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>
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
using namespace std;
const long long MAX = (long long)2e5 + 100;
long long mod = (long long)1e9 + 7, mod2 = (long long)1e9 + 9, p = 151;
long long n, m;
void solve() {
  cin >> n >> m;
  vector<string> t(n);
  vector<pair<long long, vector<string>>> ans;
  for (int i = 0; i < n; i++) cin >> t[i];
  vector<char> kek = {'A', 'G', 'C', 'T'};
  for (int i = 0; i < 24; i++) {
    vector<string> keks;
    long long price = 0;
    for (int j = 0; j < n; j++) {
      string a, b;
      if (j % 2 == 0) {
        for (int z = 0; z < m; z++) {
          if (z % 2 == 0) {
            a.push_back(kek[0]);
            b.push_back(kek[1]);
          } else {
            a.push_back(kek[1]);
            b.push_back(kek[0]);
          }
        }
      } else {
        for (int z = 0; z < m; z++) {
          if (z % 2 == 0) {
            a.push_back(kek[2]);
            b.push_back(kek[3]);
          } else {
            a.push_back(kek[3]);
            b.push_back(kek[2]);
          }
        }
      }
      long long va = 0, vb = 0;
      for (int z = 0; z < m; z++) {
        if (t[j][z] != a[z]) va++;
        if (t[j][z] != b[z]) vb++;
      }
      if (va <= vb) {
        keks.push_back(a);
        price += va;
      } else {
        keks.push_back(b);
        price += vb;
      }
    }
    ans.push_back({price, keks});
    keks.clear();
    price = 0;
    for (int j = 0; j < m; j++) {
      string a, b;
      if (j % 2 == 0) {
        for (int z = 0; z < n; z++) {
          if (z % 2 == 0) {
            a.push_back(kek[0]);
            b.push_back(kek[1]);
          } else {
            a.push_back(kek[1]);
            b.push_back(kek[0]);
          }
        }
      } else {
        for (int z = 0; z < n; z++) {
          if (z % 2 == 0) {
            a.push_back(kek[2]);
            b.push_back(kek[3]);
          } else {
            a.push_back(kek[3]);
            b.push_back(kek[2]);
          }
        }
      }
      long long va = 0, vb = 0;
      for (int z = 0; z < n; z++) {
        if (t[z][j] != a[z]) va++;
        if (t[z][j] != b[z]) vb++;
      }
      if (va <= vb) {
        keks.push_back(a);
        price += va;
      } else {
        keks.push_back(b);
        price += vb;
      }
    }
    vector<string> tmp;
    for (int i = 0; i < n; i++) {
      string mem;
      for (int j = 0; j < m; j++) {
        mem.push_back(keks[j][i]);
      }
      tmp.push_back(mem);
    }
    keks = tmp;
    ans.push_back({price, keks});
    next_permutation(kek.begin(), kek.end());
  }
  sort(ans.begin(), ans.end());
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      cout << ans[0].second[i][j];
    }
    cout << "\n";
  }
}
int main() {
  ios::sync_with_stdio(0);
  long long q;
  q = 1;
  while (q--) solve();
}
