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;
template <typename T>
void maxtt(T& t1, T t2) {
  t1 = max(t1, t2);
}
template <typename T>
void mintt(T& t1, T t2) {
  t1 = min(t1, t2);
}
bool debug = 0;
int n, m, k;
int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
string direc = "URDL";
long long ln, lk, lm;
void etp(bool f = 0) {
  puts(f ? "YES" : "NO");
  exit(0);
}
void addmod(int& x, int y, int mod = 1000000007) {
  assert(y >= 0);
  x += y;
  if (x >= mod) x -= mod;
  assert(x >= 0 && x < mod);
}
void et(int x = -1) {
  printf("%d\n", x);
  exit(0);
}
long long fastPow(long long x, long long y, int mod = 1000000007) {
  long long ans = 1;
  while (y > 0) {
    if (y & 1) ans = (x * ans) % mod;
    x = x * x % mod;
    y >>= 1;
  }
  return ans;
}
long long gcd1(long long x, long long y) { return y ? gcd1(y, x % y) : x; }
vector<int> mp[300135];
char s[300135];
string S = "AGCT";
int r[300135][2][4], col[300135][2][4];
int ans[4], id[4], A;
int gid(char x) {
  for (int(i) = 0; (i) < (int)(4); (i)++)
    if (S[i] == x) return i;
  return -1;
}
int cal(int a, int b, int c, int d, bool fg) {
  int t1 = 0, t2 = 0;
  for (int(i) = 1; (i) <= (int)(n); (i)++) {
    if (i % 2 == 1)
      t1 += max(r[i][0][a] + r[i][1][b], r[i][0][b] + r[i][1][a]);
    else
      t1 += max(r[i][0][c] + r[i][1][d], r[i][0][d] + r[i][1][c]);
  }
  if (fg && t1 == A) {
    for (int(i) = 1; (i) <= (int)(n); (i)++) {
      if (i % 2 == 1) {
        if (r[i][0][a] + r[i][1][b] < r[i][0][b] + r[i][1][a]) {
          for (int(j) = 1; (j) <= (int)(m); (j)++)
            printf("%c", j % 2 == 1 ? S[a] : S[b]);
        } else
          for (int(j) = 1; (j) <= (int)(m); (j)++)
            printf("%c", j % 2 == 1 ? S[b] : S[a]);
      } else {
        if (r[i][0][c] + r[i][1][d] < r[i][0][d] + r[i][1][c]) {
          for (int(j) = 1; (j) <= (int)(m); (j)++)
            printf("%c", j % 2 == 1 ? S[c] : S[d]);
        } else
          for (int(j) = 1; (j) <= (int)(m); (j)++)
            printf("%c", j % 2 == 1 ? S[d] : S[c]);
      }
      puts("");
    }
    exit(0);
  }
  for (int(j) = 1; (j) <= (int)(m); (j)++) {
    if (j % 2 == 1) {
      t2 += max(col[j][0][a] + col[j][1][c], col[j][0][c] + col[j][1][a]);
    } else {
      t2 += max(col[j][0][b] + col[j][1][d], col[j][0][d] + col[j][1][b]);
    }
  }
  if (fg) {
    assert(t2 == A);
    for (int(i) = 1; (i) <= (int)(n); (i)++) {
      for (int(j) = 1; (j) <= (int)(m); (j)++) {
        if (j % 2 == 1) {
          if (col[j][0][a] + col[j][1][c] < col[j][0][c] + col[j][1][a]) {
            printf("%c", i & 1 ? S[a] : S[c]);
          } else
            printf("%c", i & 1 ? S[c] : S[a]);
        } else {
          if (col[j][0][b] + col[j][1][d] < col[j][0][d] + col[j][1][b]) {
            printf("%c", i & 1 ? S[b] : S[d]);
          } else
            printf("%c", i & 1 ? S[d] : S[b]);
        }
      }
      puts("");
    }
  }
  return max(t1, t2);
}
void fmain(int tid) {
  scanf("%d%d", &n, &m);
  for (int(i) = 1; (i) <= (int)(n); (i)++) {
    mp[i].resize(m + 5, -1);
    scanf("%s", s + 1);
    for (int(j) = 1; (j) <= (int)(m); (j)++) {
      mp[i][j] = gid(s[j]);
    }
    for (int(j) = 1; (j) <= (int)(m); (j)++) {
      r[i][j % 2][mp[i][j]]++;
      col[j][i % 2][mp[i][j]]++;
    }
  }
  for (int(i) = 0; (i) < (int)(4); (i)++) id[i] = i;
  do {
    int tt = cal(id[0], id[1], id[2], id[3], 0);
    if (tt > A) {
      A = tt;
      for (int(i) = 0; (i) < (int)(4); (i)++) ans[i] = id[i];
    }
  } while (next_permutation(id, id + 4));
  cal(ans[0], ans[1], ans[2], ans[3], 1);
}
int main() {
  int t = 1;
  for (int(i) = 1; (i) <= (int)(t); (i)++) {
    fmain(i);
  }
  return 0;
}
