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 int N = 3e5 + 5, inf = 1e9;
int n, m, t, ans, anst;
int g[300], d[4];
char ch[N], c[4];
vector<int> a[2][N], b[2][N], as[2][N];
void solve(int t) {
  int i, j, k, l, s, x, y, res;
  for (i = 0; i < n; i++)
    for (j = 0; j <= m; j++) as[t][i].push_back(0), b[t][i].push_back(0);
  for (x = 0; x < 4; x++)
    for (y = x + 1; y < 4; y++) {
      res = 0;
      d[0] = x, d[1] = y;
      for (k = 2, i = 0; i < 4; i++)
        if (i != x && i != y) d[k++] = i;
      for (i = 0; i < n; i++) {
        for (s = inf, l = 0; l < 2; l++) {
          k = 0;
          for (j = 0; j < m; j++) k += d[2 * (i & 1) + (j & 1)] != a[t][i][j];
          if (s > k) {
            for (s = k, j = 0; j < m; j++)
              b[t][i][j] = d[2 * (i & 1) + (j & 1)];
          }
          swap(d[2 * (i & 1)], d[2 * (i & 1) + 1]);
        }
        res += s;
      }
      if (ans > res) {
        ans = res, anst = t;
        for (i = 0; i < n; i++)
          for (j = 0; j < m; j++) as[t][i][j] = b[t][i][j];
      }
    }
}
int main() {
  c[0] = 'A', c[1] = 'T', c[2] = 'C', c[3] = 'G';
  g['A'] = 0, g['T'] = 1, g['C'] = 2, g['G'] = 3;
  int i, j, k;
  scanf("%d%d", &n, &m);
  for (i = 0; i < n; i++)
    for (scanf("%s", &ch), j = 0; j < m; j++) a[0][i].push_back(g[ch[j]]);
  for (j = 0; j < m; j++)
    for (i = 0; i < n; i++) a[1][j].push_back(a[0][i][j]);
  ans = n * m, solve(0);
  swap(n, m), solve(1);
  swap(n, m);
  if (!anst) {
    for (i = 0; i < n; i++, puts(""))
      for (j = 0; j < m; j++) printf("%c", c[as[0][i][j]]);
  } else {
    for (i = 0; i < n; i++, puts(""))
      for (j = 0; j < m; j++) printf("%c", c[as[1][j][i]]);
  }
  return 0;
}
