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;
long long int n, m, fc = pow(10, 6), cc;
int ifr = 0;
string s1, s2, p = "AGCT";
vector<string> v, a, s;
void comp(int isr) {
  long long int i, j, rc1, rc2, f1, f2, f;
  string cs;
  cc = 0;
  if (!isr) {
    for (i = 0; i < n; i++) {
      f1 = 0;
      f2 = 1;
      rc1 = 0;
      rc2 = 0;
      cs = s1;
      if (i % 2) cs = s2;
      for (j = 0; j < m; j++) {
        if (cs[f1] - v[i][j]) rc1++;
        if (cs[f2] - v[i][j]) rc2++;
        f1 ^= 1;
        f2 ^= 1;
      }
      f1 = 0;
      f = 1;
      if (rc1 < rc2) f = f1;
      for (j = 0; j < m; j++) {
        s[i][j] = cs[f];
        f ^= 1;
      }
      cc += min(rc1, rc2);
    }
  } else {
    for (i = 0; i < m; i++) {
      f1 = 0;
      f2 = 1;
      rc1 = 0;
      rc2 = 0;
      cs = s1;
      if (i % 2) cs = s2;
      for (j = 0; j < n; j++) {
        if (cs[f1] - v[j][i]) rc1++;
        if (cs[f2] - v[j][i]) rc2++;
        f1 ^= 1;
        f2 ^= 1;
      }
      f1 = 0;
      f = 1;
      if (rc1 < rc2) f = f1;
      for (j = 0; j < n; j++) {
        s[j][i] = cs[f];
        f ^= 1;
      }
      cc += min(rc1, rc2);
    }
  }
  if (cc < fc) {
    fc = cc;
    a = s;
    ifr = isr;
  }
}
void gen(int isr) {
  long long int i, j, k;
  for (i = 0; i < 4; i++) {
    for (j = i + 1; j < 4; j++) {
      s1.clear();
      s2.clear();
      s1 += p[i];
      s1 += p[j];
      for (k = 0; k < 4; k++) {
        if (k != i && k != j) s2 += p[k];
      }
      comp(isr);
    }
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  long long int i;
  cin >> n >> m;
  v.resize(n);
  for (i = 0; i < n; i++) cin >> v[i];
  a = v;
  s = v;
  gen(0);
  gen(1);
  for (i = 0; i < n; i++) cout << a[i] << endl;
}
