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<vector<char>> a, res;
int main() {
  ios::sync_with_stdio(false);
  cin >> n >> m;
  a.assign(n + 10, vector<char>(m + 10));
  res = a;
  for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++) cin >> a[i][j];
  int ans = n * m;
  for (int t1 = 1; t1 <= 4; t1++)
    for (int t2 = 1; t2 <= 4; t2++)
      for (int t3 = 1; t3 <= 4; t3++)
        for (int t4 = 1; t4 <= 4; t4++) {
          set<int> s;
          s.insert({t1, t2, t3, t4});
          if (s.size() < 4) continue;
          map<char, int> id;
          map<int, char> di;
          id['A'] = t1, di[t1] = 'A';
          id['G'] = t2, di[t2] = 'G';
          id['C'] = t3, di[t3] = 'C';
          id['T'] = t4, di[t4] = 'T';
          int ans1 = 0, ans2 = 0;
          vector<vector<char>> x(n + 10, vector<char>(m + 10)),
              y(n + 10, vector<char>(m + 10));
          for (int i = 0, a1 = 1, a2 = 2, a3 = 3, a4 = 4; i < n;
               i++, swap(a1, a3), swap(a2, a4)) {
            int now1 = 0, now2 = 0;
            for (int j = 0, c1 = a1, c2 = a2; j < m; j++, swap(c1, c2))
              now1 += id[a[i][j]] != c1, now2 += id[a[i][j]] != c2;
            ans1 += min(now1, now2);
            for (int j = 0, c1 = a1, c2 = a2; j < m; j++, swap(c1, c2))
              x[i][j] = now1 < now2 ? di[c1] : di[c2];
          }
          for (int j = 0, a1 = 1, a2 = 2, a3 = 3, a4 = 4; j < m;
               j++, swap(a1, a3), swap(a2, a4)) {
            int now1 = 0, now2 = 0;
            for (int i = 0, c1 = a1, c2 = a2; i < n; i++, swap(c1, c2))
              now1 += id[a[i][j]] != c1, now2 += id[a[i][j]] != c2;
            ans2 += min(now1, now2);
            for (int i = 0, c1 = a1, c2 = a2; i < n; i++, swap(c1, c2))
              y[i][j] = now1 < now2 ? di[c1] : di[c2];
          }
          if (min(ans1, ans2) < ans) {
            if (ans1 < ans2)
              ans = ans1, res = x;
            else
              ans = ans2, res = y;
          }
        }
  for (int i = 0; i < n; i++, cout << '\n')
    for (int j = 0; j < m; j++) cout << res[i][j];
  return 0;
}
