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 MAXN = 3e5 + 10;
int r, s, best = 1e9 + 10;
int pref_row[MAXN], suff_row[MAXN], pref_col[MAXN], suff_col[MAXN];
vector<string> grid, sol, nxt;
inline void clear() {
  for (int i = 0; i < r; ++i) {
    for (int j = 0; j < s; ++j) nxt[i][j] = '.';
  }
}
void check_best() {
  int dist = 0;
  for (int i = 0; i < r; ++i)
    for (int j = 0; j < s; ++j) dist += nxt[i][j] != grid[i][j];
  if (dist < best) {
    best = dist;
    sol = nxt;
  }
}
void fill_grid(const string &p, int rr, int ss) {
  clear();
  for (int i = 0; i < 4; ++i) nxt[i / 2][i % 2] = p[i];
  if (rr == -1 && ss == -1) {
    for (int i = 0; i < r; ++i)
      for (int j = 0; j < s; ++j) nxt[i][j] = nxt[i % 2][j % 2];
    check_best();
    return;
  }
  if (ss != -1) {
    for (int j = 2; j < ss; ++j) {
      nxt[0][j] = nxt[0][j - 2];
      nxt[1][j] = nxt[1][j - 2];
    }
    nxt[0][ss] = nxt[1][ss - 2];
    nxt[1][ss] = nxt[0][ss - 2];
    for (int i = 2; i < r; ++i)
      for (int j = 0; j <= ss; ++j) nxt[i][j] = nxt[i - 2][j];
    for (int j = ss + 1; j < s; ++j) {
      int a = 0, b = 0;
      for (int i = 0; i < r; ++i) {
        a += grid[i][j] != nxt[i % 2][j % 2];
        b += grid[i][j] != nxt[(i + 1) % 2][j % 2];
      }
      for (int i = 0; i < r; ++i)
        if (a < b)
          nxt[i][j] = nxt[i % 2][j % 2];
        else
          nxt[i][j] = nxt[(i + 1) % 2][j % 2];
    }
  } else {
    for (int i = 2; i < rr; ++i) {
      nxt[i][0] = nxt[i - 2][0];
      nxt[i][1] = nxt[i - 2][1];
    }
    nxt[rr][0] = nxt[rr - 2][1];
    nxt[rr][1] = nxt[rr - 2][0];
    for (int j = 2; j < s; ++j)
      for (int i = 0; i <= rr; ++i) nxt[i][j] = nxt[i][j - 2];
    for (int i = rr + 1; i < r; ++i) {
      int a = 0, b = 0;
      for (int j = 0; j < s; ++j) {
        a += grid[i][j] != nxt[i % 2][j % 2];
        b += grid[i][j] != nxt[i % 2][(j + 1) % 2];
      }
      for (int j = 0; j < s; ++j) {
        if (a < b)
          nxt[i][j] = nxt[i % 2][j % 2];
        else
          nxt[i][j] = nxt[i % 2][(j + 1) % 2];
      }
    }
  }
  check_best();
}
void init(const string &p) {
  char P[3][3];
  for (int i = 0; i < 4; ++i) P[i / 2][i % 2] = p[i];
  for (int i = 0; i < r; ++i) {
    int dist = 0;
    for (int j = 0; j < s; ++j) dist += grid[i][j] != P[i % 2][j % 2];
    pref_row[i] = dist;
    if (i > 0) pref_row[i] += pref_row[i - 1];
  }
  for (int i = r - 1; i >= 0; --i) {
    int a = 0, b = 0;
    for (int j = 0; j < s; ++j) {
      a += grid[i][j] != P[i % 2][j % 2];
      b += grid[i][j] != P[i % 2][(j + 1) % 2];
    }
    suff_row[i] = min(a, b);
    suff_row[i] += suff_row[i + 1];
  }
  for (int j = 0; j < s; ++j) {
    int dist = 0;
    for (int i = 0; i < r; ++i) dist += grid[i][j] != P[i % 2][j % 2];
    pref_col[j] = dist;
    if (j > 0) pref_col[j] += pref_col[j - 1];
  }
  for (int j = s - 1; j >= 0; --j) {
    int a = 0, b = 0;
    for (int i = 0; i < r; ++i) {
      a += grid[i][j] != P[i % 2][j % 2];
      b += grid[i][j] != P[(i + 1) % 2][j % 2];
    }
    suff_col[j] = min(a, b);
    suff_col[j] += suff_col[j + 1];
  }
}
void solve_grid(const string &p) {
  init(p);
  int rr = -1, ss = -1;
  int curr = pref_row[r];
  char P[3][3];
  for (int i = 0; i < 4; ++i) P[i / 2][i % 2] = p[i];
  int _best = best;
  for (int i = 2; i < r; ++i) {
    int rev = 0;
    for (int j = 0; j < s; ++j) rev += grid[i][j] != P[i % 2][(j + 1) % 2];
    if (pref_row[i - 1] + rev + suff_row[i + 1] < _best) {
      _best = pref_row[i - 1] + rev + suff_row[i + 1];
      rr = i;
      ss = -1;
    }
  }
  for (int j = 2; j < s; ++j) {
    int rev = 0;
    for (int i = 0; i < r; ++i) rev += grid[i][j] != P[(i + 1) % 2][j % 2];
    if (pref_col[j - 1] + rev + suff_col[j + 1] < _best) {
      _best = pref_col[j - 1] + rev + suff_col[j + 1];
      rr = -1;
      ss = j;
    }
  }
  fill_grid(p, rr, ss);
}
int main(void) {
  ios::sync_with_stdio(false);
  cin >> r >> s;
  for (int i = 0; i < r; ++i) {
    string str;
    cin >> str;
    grid.push_back(str);
  }
  string perm = "ACGT";
  nxt = grid;
  do {
    fill_grid(perm, -1, -1);
    solve_grid(perm);
  } while (next_permutation(perm.begin(), perm.end()));
  for (int i = 0; i < r; ++i) cout << sol[i] << endl;
  return 0;
}
