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;
void getint(int &v) {
  char ch, fu = 0;
  for (ch = '*'; (ch < '0' || ch > '9') && ch != '-'; ch = getchar())
    ;
  if (ch == '-') fu = 1, ch = getchar();
  for (v = 0; ch >= '0' && ch <= '9'; ch = getchar()) v = v * 10 + ch - '0';
  if (fu) v = -v;
}
const int INF = 1e9 + 10;
char s[500010];
int C[55555], ts, tmp[333], c[2][300010][4];
vector<int> a[300010], now[300010], ANS[300010];
pair<int, int> g[300010][4][4];
int n, m, f[300010][4][4], ans;
int main() {
  cin >> n >> m;
  C['A'] = 0;
  C['T'] = 1;
  C['C'] = 2;
  C['G'] = 3;
  for (int i = 1; i <= n; ++i) {
    scanf("%s", s + 1);
    a[i].push_back(0);
    for (int j = 1; j <= m; ++j) a[i].push_back(C[s[j]]);
  }
  ans = INF;
  for (int i = 0; i <= n; ++i) now[i].resize(m + 1), ANS[i].resize(m + 1);
  for (int X = 0; X <= 3; ++X)
    for (int Y = X + 1; Y <= 3; ++Y) {
      int t = 0;
      int XX = -1, YY = -1;
      for (int t = 0; t <= 3; ++t)
        if (t != X && t != Y) {
          if (XX == -1)
            XX = t;
          else
            YY = t;
        }
      for (int j = 1; j <= m; ++j)
        if (j & 1) {
          int t1 = 0, t2 = 0;
          for (int i = 1; i <= n; ++i) {
            if ((i & 1) && (a[i][j] != X)) ++t1;
            if ((i & 1) && (a[i][j] != Y)) ++t2;
            if (!(i & 1) && (a[i][j] != Y)) ++t1;
            if (!(i & 1) && (a[i][j] != X)) ++t2;
          }
          t += min(t1, t2);
          if (t1 <= t2) {
            for (int i = 1; i <= n; ++i)
              if (i & 1)
                now[i][j] = X;
              else
                now[i][j] = Y;
          } else {
            for (int i = 1; i <= n; ++i)
              if (i & 1)
                now[i][j] = Y;
              else
                now[i][j] = X;
          }
        } else {
          int t1 = 0, t2 = 0;
          for (int i = 1; i <= n; ++i) {
            if ((i & 1) && (a[i][j] != XX)) ++t1;
            if ((i & 1) && (a[i][j] != YY)) ++t2;
            if (!(i & 1) && (a[i][j] != YY)) ++t1;
            if (!(i & 1) && (a[i][j] != XX)) ++t2;
          }
          t += min(t1, t2);
          if (t1 <= t2) {
            for (int i = 1; i <= n; ++i)
              if (i & 1)
                now[i][j] = XX;
              else
                now[i][j] = YY;
          } else {
            for (int i = 1; i <= n; ++i)
              if (i & 1)
                now[i][j] = YY;
              else
                now[i][j] = XX;
          }
        }
      if (t < ans) {
        ans = t;
        for (int i = 1; i <= n; ++i)
          for (int j = 1; j <= m; ++j) ANS[i][j] = now[i][j];
      }
    }
  for (int rp = 0; rp <= 1; ++rp)
    for (int i = 1; i <= n; ++i)
      for (int h = 0; h <= 3; ++h) {
        for (int j = 1; j <= m; ++j)
          if (j % 2 == rp) {
            if (a[i][j] != h) ++c[rp][i][h];
          }
      }
  for (int i = 1; i <= n; ++i)
    for (int j = 0; j <= 3; ++j)
      for (int k = 0; k <= 3; ++k) f[i][j][k] = INF;
  for (int i = 0; i <= 3; ++i)
    for (int j = 0; j <= 3; ++j)
      if (i != j) f[1][i][j] = c[1][1][i] + c[0][1][j];
  for (int i = 1; i <= n - 1; ++i)
    for (int j = 0; j <= 3; ++j)
      for (int k = 0; k <= 3; ++k)
        if (j != k && f[i][j][k] < INF) {
          ts = 0;
          for (int t = 0; t <= 3; ++t)
            if (t != j && t != k) tmp[++ts] = t;
          if (f[i][j][k] + c[1][i + 1][tmp[1]] + c[0][i + 1][tmp[2]] <
              f[i + 1][tmp[1]][tmp[2]]) {
            f[i + 1][tmp[1]][tmp[2]] =
                f[i][j][k] + c[1][i + 1][tmp[1]] + c[0][i + 1][tmp[2]];
            g[i + 1][tmp[1]][tmp[2]] = make_pair(j, k);
          }
          if (f[i][j][k] + c[1][i + 1][tmp[2]] + c[0][i + 1][tmp[1]] <
              f[i + 1][tmp[2]][tmp[1]]) {
            f[i + 1][tmp[2]][tmp[1]] =
                f[i][j][k] + c[1][i + 1][tmp[2]] + c[0][i + 1][tmp[1]];
            g[i + 1][tmp[2]][tmp[1]] = make_pair(j, k);
          }
        }
  for (int j = 0; j <= 3; ++j)
    for (int k = 0; k <= 3; ++k)
      if (j != k && f[n][j][k] < ans) {
        ans = min(ans, f[n][j][k]);
        int t = n;
        int J = j, K = k;
        while (1) {
          for (int o = 1; o <= m; ++o)
            if (o & 1)
              ANS[t][o] = J;
            else
              ANS[t][o] = K;
          if (t == 1) break;
          pair<int, int> tmp = g[t][J][K];
          J = tmp.first;
          K = tmp.second;
          --t;
        }
      }
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= m; ++j)
      if (ANS[i][j] == 0)
        putchar('A');
      else if (ANS[i][j] == 1)
        putchar('T');
      else if (ANS[i][j] == 2)
        putchar('C');
      else
        putchar('G');
    puts("");
  }
  return 0;
}
