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;
int n, m, t1, t2, minres = 0x7ffffff;
char t[300009], tmp,
    sa[7][2][2] = {{0},
                   {{'A', 'T'}, {'C', 'G'}},
                   {{'A', 'C'}, {'T', 'G'}},
                   {{'A', 'G'}, {'C', 'T'}},
                   {{'T', 'C'}, {'A', 'G'}},
                   {{'T', 'G'}, {'A', 'C'}},
                   {{'C', 'G'}, {'A', 'T'}}};
bool re[300009], tm[300009];
int main() {
  int n, m, res1, res2, res3, total;
  scanf("%d%d", &n, &m);
  for (int i = (1), ilim = (n); i <= ilim; i++)
    for (int j = (1), jlim = (m); j <= jlim; j++) {
      tmp = 0;
      while (!isalpha(tmp)) tmp = getchar();
      t[(i - 1) * m + j] = tmp;
    }
  for (int i = (1), ilim = (6); i <= ilim; i++) {
    total = 0;
    for (int j = (1), jlim = (n); j <= jlim; j++) {
      res1 = res2 = res3 = 0;
      for (int k = (1), klim = (m); k <= klim; k++) {
        if (t[(j - 1) * m + k] == sa[i][j & 1][k & 1])
          res2++;
        else if (t[(j - 1) * m + k] == sa[i][j & 1][1 ^ (k & 1)])
          res1++;
        else
          res3++;
      }
      if (res1 < res2) {
        tm[j] = 0;
      } else {
        res1 = res2;
        tm[j] = 1;
      }
      total += res1 + res3;
    }
    if (total < minres) {
      minres = total;
      memcpy(re, tm, n + 1);
      t1 = 0;
      t2 = i;
    }
  }
  for (int i = (1), ilim = (6); i <= ilim; i++) {
    total = 0;
    for (int j = (1), jlim = (m); j <= jlim; j++) {
      res1 = res2 = res3 = 0;
      for (int k = (1), klim = (n); k <= klim; k++) {
        if (t[(k - 1) * m + j] == sa[i][j & 1][k & 1])
          res2++;
        else if (t[(k - 1) * m + j] == sa[i][j & 1][1 ^ (k & 1)])
          res1++;
        else
          res3++;
      }
      if (res1 < res2) {
        tm[j] = 0;
      } else {
        res1 = res2;
        tm[j] = 1;
      }
      total += res1 + res3;
    }
    if (total < minres) {
      minres = total;
      memcpy(re, tm, m + 1);
      t1 = 1;
      t2 = i;
    }
  }
  for (int i = (1), ilim = (n); i <= ilim; i++) {
    for (int j = (1), jlim = (m); j <= jlim; j++) {
      if (t1) {
        t[(i - 1) * m + j] = sa[t2][j & 1][re[j] ^ (i & 1)];
      } else {
        t[(i - 1) * m + j] = sa[t2][i & 1][re[i] ^ (j & 1)];
      }
      printf("%c", t[(i - 1) * m + j]);
    }
    putchar('\n');
  }
  return 0;
}
