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 long long mod = 1e9 + 7;
int n, m, mnr = 1e9, mnc = 1e9;
vector<char> cr;
vector<string> ans, ans1;
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  cr.push_back('A');
  cr.push_back('G');
  cr.push_back('C');
  cr.push_back('T');
  cin >> n >> m;
  char gr[n + 3][m + 3];
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      cin >> gr[i][j];
    }
  }
  for (int z = 0; z < 4; z++) {
    for (int k = 0; k < 4; k++) {
      vector<string> v;
      int dif = 0, dif1 = 0, dif2 = 0;
      if (z == k) continue;
      for (int i = 0; i < n; i++) {
        string s, s1;
        if (i % 2 == 0) {
          s.push_back(cr[z]);
          s.push_back(cr[k]);
        } else {
          for (int zz = 0; zz < 4; zz++) {
            for (int kk = 0; kk < 4; kk++) {
              if (z != zz && k != kk && z != kk && k != zz && zz != kk) {
                s.push_back(cr[zz]);
                s.push_back(cr[kk]);
                break;
              }
            }
            if (s.size() > 0) break;
          }
        }
        for (int j = 0; j < m; j++) {
          if (j > 1) s.push_back(s[j - 2]);
          if (s[j] != gr[i][j]) dif1++;
        }
        if (i % 2 == 0) {
          s1.push_back(cr[k]);
          s1.push_back(cr[z]);
        } else {
          for (int zz = 0; zz < 4; zz++) {
            for (int kk = 0; kk < 4; kk++) {
              if (z != zz && k != kk && z != kk && k != zz && zz != kk) {
                s1.push_back(cr[kk]);
                s1.push_back(cr[zz]);
                break;
              }
            }
            if (s1.size() > 0) break;
          }
        }
        for (int j = 0; j < m; j++) {
          if (j > 1) s1.push_back(s1[j - 2]);
          if (s1[j] != gr[i][j]) dif2++;
        }
        if (dif1 > dif2)
          v.push_back(s1);
        else
          v.push_back(s);
        dif += min(dif1, dif2);
        dif1 = 0, dif2 = 0;
      }
      if (mnr > dif) ans = v;
      mnr = min(mnr, dif);
      dif = 0;
      v.clear();
    }
  }
  for (int z = 0; z < 4; z++) {
    for (int k = 0; k < 4; k++) {
      vector<string> v;
      int dif = 0, dif1 = 0, dif2 = 0;
      if (z == k) continue;
      for (int i = 0; i < m; i++) {
        string s, s1;
        if (i % 2 == 0) {
          s.push_back(cr[z]);
          s.push_back(cr[k]);
        } else {
          for (int zz = 0; zz < 4; zz++) {
            for (int kk = 0; kk < 4; kk++) {
              if (z != zz && k != kk && z != kk && k != zz && zz != kk) {
                s.push_back(cr[zz]);
                s.push_back(cr[kk]);
                break;
              }
            }
            if (s.size() > 0) break;
          }
        }
        for (int j = 0; j < n; j++) {
          if (j > 1) s.push_back(s[j - 2]);
          if (s[j] != gr[j][i]) dif1++;
        }
        if (i % 2 == 0) {
          s1.push_back(cr[k]);
          s1.push_back(cr[z]);
        } else {
          for (int zz = 0; zz < 4; zz++) {
            for (int kk = 0; kk < 4; kk++) {
              if (z != zz && k != kk && z != kk && k != zz && zz != kk) {
                s1.push_back(cr[kk]);
                s1.push_back(cr[zz]);
                break;
              }
            }
            if (s1.size() > 0) break;
          }
        }
        for (int j = 0; j < n; j++) {
          if (j > 1) s1.push_back(s1[j - 2]);
          if (s1[j] != gr[j][i]) dif2++;
        }
        if (dif1 > dif2)
          v.push_back(s1);
        else
          v.push_back(s);
        dif += min(dif1, dif2);
        dif1 = 0, dif2 = 0;
      }
      if (mnc > dif) ans1 = v;
      mnc = min(mnc, dif);
      dif = 0;
      v.clear();
    }
  }
  if (mnr < mnc)
    for (int i = 0; i < ans.size(); i++) cout << ans[i] << endl;
  else {
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        cout << ans1[j][i];
      }
      cout << endl;
    }
  }
}
