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;
string s[300005];
string tmpS[300005];
int best = 300005;
int rn, rm;
string res[300005];
string curS[300005];
char chars[] = {'A', 'C', 'G', 'T'};
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cin >> n >> m;
  for (int i = 0; i < n; ++i) {
    cin >> s[i];
    tmpS[i] = s[i];
  }
  for (int iter = 0; iter < 2; ++iter) {
    sort(chars, chars + 4);
    do {
      int curVal = 0;
      for (int i = 0; i < n; ++i) {
        string tmp = "";
        tmp += chars[2 * (i % 2)];
        tmp += chars[2 * (i % 2) + 1];
        string bestS;
        int bestRes = 300005;
        for (int t = 0; t < 2; ++t) {
          int cur = 0;
          for (int j = 0; j < m; ++j)
            if (tmp[j % 2] != s[i][j]) ++cur;
          if (cur < bestRes) {
            bestRes = cur;
            bestS = tmp;
          }
          swap(tmp[0], tmp[1]);
        }
        curVal += bestRes;
        curS[i] = "";
        for (int j = 0; j < m; ++j) curS[i] += bestS[j % 2];
      }
      if (curVal < best) {
        best = curVal;
        rn = n;
        rm = m;
        for (int i = 0; i < n; ++i) res[i] = curS[i];
      }
    } while (next_permutation(chars, chars + 4));
    for (int j = 0; j < m; ++j) {
      s[j] = "";
      for (int i = 0; i < n; ++i) s[j] += tmpS[i][j];
    }
    swap(n, m);
  }
  if (rn == n) {
    for (int i = 0; i < n; ++i) cout << res[i] << endl;
  } else {
    for (int i = 0; i < rm; ++i) {
      for (int j = 0; j < rn; ++j) cout << res[j][i];
      cout << endl;
    }
  }
  return 0;
}
