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;
string a[300010], b[300010], answer[300010];
char ch[5] = "AGCT";
int f[2][4][4][300010];
int ans, ans1, ans2, ans3;
inline void solve(int n, int m, int opt) {
  for (int x = 0; x < 4; ++x)
    for (int y = 0; y < 4; ++y)
      if (x != y) {
        char c1 = ch[x], c2 = ch[y];
        for (int i = 1; i <= n; ++i) {
          int s = 0;
          for (int j = 1; j <= m; ++j)
            if (j & 1)
              s += a[i][j] != c1;
            else
              s += a[i][j] != c2;
          f[opt][x][y][i] = s;
        }
      }
  for (int x = 0; x < 4; ++x)
    for (int y = 0; y < 4; ++y)
      if (x != y) {
        int z, w;
        for (z = 0; z < 4; ++z)
          if (z != x && z != y) break;
        for (w = 0; w < 4; ++w)
          if (w != x && w != y && w != z) break;
        char c1 = ch[x], c2 = ch[y], c3 = ch[z], c4 = ch[w];
        int s = f[opt][x][y][1];
        for (int i = 2; i <= n; ++i)
          if (i & 1)
            s += min(f[opt][x][y][i], f[opt][y][x][i]);
          else
            s += min(f[opt][z][w][i], f[opt][w][z][i]);
        if (s < ans) {
          ans = s;
          ans1 = x;
          ans2 = y;
          ans3 = opt;
        }
      }
}
int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  ans = n * m;
  for (int i = 1; i <= n; ++i) {
    cin >> b[i];
    a[i].resize(m + 5);
    answer[i].resize(m + 5);
  }
  for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= m; ++j) a[i][j] = b[i][j - 1];
  solve(n, m, 0);
  for (int i = 1; i <= m; ++i) {
    a[i].clear();
    a[i].resize(n + 5);
  }
  for (int i = 1; i <= m; ++i)
    for (int j = 1; j <= n; ++j) a[i][j] = b[j][i - 1];
  solve(m, n, 1);
  int x = ans1, y = ans2;
  int z, w;
  for (z = 0; z < 4; ++z)
    if (z != x && z != y) break;
  for (w = 0; w < 4; ++w)
    if (w != x && w != y && w != z) break;
  if (ans3) {
    for (int i = 1; i <= m; ++i)
      if (i & 1) {
        if (f[ans3][x][y][i] > f[ans3][y][x][i]) swap(x, y);
        for (int j = 1; j <= n; ++j) {
          if (j & 1)
            answer[j][i] = ch[x];
          else
            answer[j][i] = ch[y];
        }
      } else {
        if (f[ans3][z][w][i] > f[ans3][w][z][i]) swap(z, w);
        for (int j = 1; j <= n; ++j) {
          if (j & 1)
            answer[j][i] = ch[z];
          else
            answer[j][i] = ch[w];
        }
      }
  } else {
    for (int i = 1; i <= n; ++i)
      if (i & 1) {
        if (f[ans3][x][y][i] > f[ans3][y][x][i]) swap(x, y);
        for (int j = 1; j <= m; ++j) {
          if (j & 1)
            answer[i][j] = ch[x];
          else
            answer[i][j] = ch[y];
        }
      } else {
        if (f[ans3][z][w][i] > f[ans3][w][z][i]) swap(z, w);
        for (int j = 1; j <= m; ++j) {
          if (j & 1)
            answer[i][j] = ch[z];
          else
            answer[i][j] = ch[w];
        }
      }
  }
  for (int i = 1; i <= n; ++i, printf("\n"))
    for (int j = 1; j <= m; ++j) printf("%c", answer[i][j]);
}
