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;
vector<string> grid, res;
string ch = "ACGT", bch;
vector<int> DP[2], nxt[2];
int solve(const int idx, const bool turned, const bool t) {
  if (DP[turned][idx] != -1) return DP[turned][idx];
  if (idx == n) return 0;
  int tot = 0;
  for (int i = 0; i < m; i++)
    tot += ((!t ? grid[idx][i] : grid[i][idx]) ==
            ch[((idx & 1) << 1) + ((turned + i) & 1)]);
  int ret1 = solve(idx + 1, 0, t);
  int ret2 = solve(idx + 1, 1, t);
  if (!nxt[0].empty()) nxt[turned][idx] = (ret2 > ret1);
  return DP[turned][idx] = tot + max(ret1, ret2);
}
int main() {
  ios::sync_with_stdio(0);
  int ret, best = 0, st, sw;
  cin >> n >> m;
  grid.assign(n + 1, ""), res.assign(n + 5, "");
  for (int i = 0; i < n; i++) cin >> grid[i];
  do {
    for (int i = 0; i < 2; i++) {
      for (int j = 0; j < 2; j++) {
        DP[0].assign(n + 5, -1), DP[1].assign(n + 5, -1);
        if ((ret = solve(0, i, j)) > best) best = ret, bch = ch, st = i, sw = j;
        swap(n, m);
      }
    }
  } while (next_permutation(ch.begin(), ch.end()));
  if (sw) swap(n, m);
  ch = bch, DP[0].assign(n + 5, -1), DP[1].assign(n + 5, -1),
  nxt[0].assign(n + 5, -1), nxt[1].assign(n + 5, -1), solve(0, st, sw);
  int curr = 0;
  while (curr != n) {
    for (int i = 0; i < m; i++)
      res[!sw ? curr : i].push_back(bch[((curr & 1) << 1) + ((st + i) & 1)]);
    st = nxt[st][curr++];
  }
  for (int i = 0; i < (sw ? m : n); i++) cout << res[i] << endl;
  return 0;
}
