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 + 10, M = 15;
int jl[M][N], zf[M][N], ans = 3e5 + 10, res = 0, fk = -1, cnt = 0, n, m;
int fa[6][2] = {{1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4}};
vector<int> qx[N];
string lx[N];
char zh(int z) {
  if (z == 1) return 'A';
  if (z == 2) return 'G';
  if (z == 3) return 'T';
  if (z == 4) return 'C';
}
int hz(char ch) {
  if (ch == 'A') return 1;
  if (ch == 'G') return 2;
  if (ch == 'T') return 3;
  if (ch == 'C') return 4;
}
void out() {
  if (fk) {
    for (int i = 1; i <= n; ++i) {
      int nw = jl[res][i];
      for (int j = 0; j <= m - 1; ++j) {
        int kk = j & 1;
        if (zf[res][i] < 0) kk = 1 - kk;
        qx[i].push_back(fa[nw][kk]);
      }
    }
  } else {
    for (int i = 0; i <= m - 1; ++i) {
      int nw = jl[res][i];
      for (int j = 1; j <= n; ++j) {
        int kk = j & 1;
        if (!zf[res][i]) kk = 1 - kk;
        qx[j].push_back(fa[nw][kk]);
      }
    }
  }
  for (int i = 1; i <= n; ++i) {
    for (int j = 0; j <= m - 1; ++j) cout << zh(qx[i][j]);
    cout << "\n";
  }
}
int main() {
  cin >> n >> m;
  for (int i = 1; i <= n; ++i) cin >> lx[i];
  for (int i = 0; i <= 5; ++i) {
    ++cnt;
    int pos = 0, ds = i, fs = 5 - i;
    for (int j = 1; j <= n; ++j) {
      if (j & 1) {
        int zx = 0, nx = 0;
        for (int k = 0; k <= m - 1; ++k) {
          int nw = hz(lx[j][k]), zz = k & 1;
          if (fa[ds][zz] != nw) zx++;
          if (fa[ds][1 - zz] != nw) nx++;
        }
        pos += min(zx, nx);
        if (zx < nx)
          jl[cnt][j] = ds;
        else
          jl[cnt][j] = ds, zf[cnt][j] = -1;
      } else {
        int zx = 0, nx = 0;
        for (int k = 0; k <= m - 1; ++k) {
          int nw = hz(lx[j][k]), zz = k & 1;
          if (fa[fs][zz] != nw) zx++;
          if (fa[fs][1 - zz] != nw) nx++;
        }
        pos += min(zx, nx);
        if (zx < nx)
          jl[cnt][j] = fs;
        else
          jl[cnt][j] = fs, zf[cnt][j] = -1;
      }
    }
    if (pos < ans) ans = pos, fk = 1, res = cnt;
  }
  for (int i = 0; i <= 5; ++i) {
    ++cnt;
    int pos = 0, ds = i, fs = 5 - i;
    for (int j = 0; j <= m - 1; ++j) {
      if (j & 1) {
        int zx = 0, nx = 0;
        for (int k = 1; k <= n; ++k) {
          int nw = hz(lx[k][j]), zz = k & 1;
          if (fa[ds][zz] != nw) nx++;
          if (fa[ds][zz ^ 1] != nw) zx++;
        }
        pos += min(zx, nx);
        if (zx < nx)
          jl[cnt][j] = ds;
        else
          jl[cnt][j] = ds, zf[cnt][j] = -1;
      } else {
        int zx = 0, nx = 0;
        for (int k = 1; k <= n; ++k) {
          int nw = hz(lx[k][j]), zz = k & 1;
          if (fa[fs][zz] != nw) nx++;
          if (fa[fs][zz ^ 1] != nw) zx++;
        }
        pos += min(zx, nx);
        if (zx < nx)
          jl[cnt][j] = fs;
        else
          jl[cnt][j] = fs, zf[cnt][j] = -1;
      }
    }
    if (pos < ans) ans = pos, res = cnt, fk = 0;
  }
  out();
  return 0;
}
