You are given an n × m table, consisting of characters «A», «G», «C», «T». Let's call a table nice, if every 2 × 2 square contains all four distinct characters. Your task is to find a nice table (also consisting of «A», «G», «C», «T»), that differs from the given table in the minimum number of characters.

Input

First line contains two positive integers n and m — number of rows and columns in the table you are given (2 ≤ n, m, n × m ≤ 300 000). Then, n lines describing the table follow. Each line contains exactly m characters «A», «G», «C», «T».

Output

Output n lines, m characters each. This table must be nice and differ from the input table in the minimum number of characters.

Examples

Input


2 2
AG
CT


Output


AG
CT


Input


3 5
AGCAG
AGCAG
AGCAG


Output


TGCAT
CATGC
TGCAT

Note

In the first sample, the table is already nice. In the second sample, you can change 9 elements to make the table nice.
#include <bits/stdc++.h>
using namespace std;
const long long N = 3e5 + 5;
int n, m;
string second[N];
string s[N];
int pas = N + 5;
string ans[N];
char ch[4] = {'A', 'C', 'G', 'T'};
int a[4];
int A[2];
int main() {
  ios::sync_with_stdio(false);
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    cin >> second[i];
    second[i] = "#" + second[i];
    s[i] = second[i];
    ans[i] = second[i];
  }
  for (a[0] = 0; a[0] < 4; a[0]++)
    for (a[1] = a[0] + 1; a[1] < 4; a[1]++)
      for (a[2] = 0; a[2] < 4; a[2]++)
        if (a[0] != a[2] && a[1] != a[2]) {
          a[3] = 6 - a[0] - a[1] - a[2];
          if (a[3] < a[2]) continue;
          for (int I = 0; I < 4; I += 2) {
            for (int i = 1 + I / 2; i <= n; i += 2) {
              int x = 0, y = 0;
              for (int j = 1; j <= m; j++) {
                if (second[i][j] == ch[a[I + j % 2]]) x++;
                if (second[i][j] == ch[a[I + 1 - j % 2]]) y++;
              }
              A[0] = a[I];
              A[1] = a[I + 1];
              if (x < y) swap(A[0], A[1]);
              for (int j = 1; j <= m; j++) s[i][j] = ch[A[j % 2]];
            }
          }
          int c = 0;
          for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
              if (s[i][j] != second[i][j]) c++;
          if (c < pas) {
            pas = c;
            for (int i = 1; i <= n; i++) ans[i] = s[i];
          }
        }
  for (a[0] = 0; a[0] < 4; a[0]++)
    for (a[1] = a[0] + 1; a[1] < 4; a[1]++)
      for (a[2] = 0; a[2] < 4; a[2]++)
        if (a[0] != a[2] && a[1] != a[2]) {
          a[3] = 6 - a[0] - a[1] - a[2];
          if (a[3] < a[2]) continue;
          for (int I = 0; I < 4; I += 2) {
            for (int i = 1 + I / 2; i <= m; i += 2) {
              int x = 0, y = 0;
              for (int j = 1; j <= n; j++) {
                if (second[j][i] == ch[a[I + j % 2]]) x++;
                if (second[j][i] == ch[a[I + 1 - j % 2]]) y++;
              }
              A[0] = a[I];
              A[1] = a[I + 1];
              if (x < y) swap(A[0], A[1]);
              for (int j = 1; j <= n; j++) s[j][i] = ch[A[j % 2]];
            }
          }
          int c = 0;
          for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
              if (s[i][j] != second[i][j]) c++;
          if (c < pas) {
            pas = c;
            for (int i = 1; i <= n; i++) ans[i] = s[i];
          }
        }
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) cout << ans[i][j];
    cout << endl;
  }
  return 0;
}
