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;
vector<vector<int>> mat;
vector<vector<int>> transpose(vector<vector<int>> v) {
  int r = v.size(), c = v[0].size();
  vector<vector<int>> nw(c);
  int temp, temp2;
  for (temp = 0; temp < r; temp++)
    for (temp2 = 0; temp2 < c; temp2++) nw[temp2].push_back(v[temp][temp2]);
  return nw;
}
string s = "ACGT";
void printmat(vector<vector<int>> v) {
  for (auto lel : v) {
    for (auto lol : lel) cout << s[lol];
    cout << "\n";
  }
}
int getdiff(vector<int> &v1, vector<int> &v2) {
  int cnt = 0;
  for (int temp = 0; temp < v1.size(); temp++) cnt += (v1[temp] != v2[temp]);
  return cnt;
}
int main() {
  int n, m, temp, temp2;
  cin >> n >> m;
  int hsh[200];
  hsh['A'] = 0;
  hsh['C'] = 1;
  hsh['G'] = 2;
  hsh['T'] = 3;
  vector<vector<int>> a(n);
  for (temp = 0; temp < n; temp++) {
    for (temp2 = 0; temp2 < m; temp2++) {
      char c;
      cin >> c;
      a[temp].push_back(hsh[c]);
    }
  }
  bool istranspose = false;
  if (n > m) {
    istranspose = true;
    a = transpose(a);
    swap(n, m);
  }
  int cost[n][2][4];
  for (temp = 0; temp < n; temp++) {
    for (temp2 = 0; temp2 < 2; temp2++) {
      for (int temp3 = 0; temp3 < 4; temp3++) {
        cost[temp][temp2][temp3] = 0;
        for (int temp4 = temp2; temp4 < m; temp4 += 2) {
          cost[temp][temp2][temp3] += (a[temp][temp4] != temp3);
        }
      }
    }
  }
  vector<int> v = {0, 1, 2, 3};
  int ans = 10e8;
  vector<vector<int>> jwb;
  do {
    vector<int> vv[2][2];
    for (temp = 0; temp < m; temp++) {
      vv[0][0].push_back(v[temp % 2]);
      vv[0][1].push_back(v[1 - temp % 2]);
      vv[1][0].push_back(v[temp % 2 + 2]);
      vv[1][1].push_back(v[3 - temp % 2]);
    }
    int mn = 0;
    vector<vector<int>> opt;
    for (temp = 0; temp < n; temp++) {
      int lamin = 10e8;
      vector<int> optin;
      for (int tmp = 0; tmp < 2; tmp++) {
        int dst = getdiff(vv[temp % 2][tmp], a[temp]);
        if (dst < lamin) {
          optin = vv[temp % 2][tmp];
          lamin = dst;
        }
      }
      opt.push_back(optin);
      mn += lamin;
    }
    if (mn < ans) {
      ans = mn;
      jwb = opt;
    }
    mn = 0;
    opt.clear();
    opt.resize(n);
    for (int tmp = 0; tmp < 2; tmp++) {
      for (int tmp2 = 0; tmp2 < 2; tmp2++) {
        vv[tmp][tmp2].clear();
      }
    }
    for (temp = 0; temp < n; temp++) {
      int a = v[0], b = v[2], c = v[1], d = v[3];
      if (temp % 2 == 1) {
        swap(a, b);
        swap(c, d);
      }
      vv[0][0].push_back(a);
      vv[0][1].push_back(b);
      vv[1][0].push_back(c);
      vv[1][1].push_back(d);
    }
    for (temp = 0; temp < m; temp++) {
      int lamin = 10e8;
      vector<int> curbar, optin;
      for (temp2 = 0; temp2 < n; temp2++) curbar.push_back(a[temp2][temp]);
      for (int tmp = 0; tmp < 2; tmp++) {
        int dst = getdiff(vv[temp % 2][tmp], curbar);
        if (dst < lamin) {
          lamin = dst;
          optin = vv[temp % 2][tmp];
        }
      }
      for (temp2 = 0; temp2 < n; temp2++) {
        opt[temp2].push_back(optin[temp2]);
      }
      mn += lamin;
    }
    if (mn < ans) {
      ans = mn;
      jwb = opt;
    }
  } while (next_permutation(v.begin(), v.end()));
  if (istranspose) jwb = transpose(jwb);
  printmat(jwb);
}
