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;
using ull = uint64_t;
using ll = int64_t;
using ld = long double;
string st = "AGCT";
const int N = 300228;
string s[N];
string t[N];
string best[N];
string curr[N];
int n, m;
int ans = N;
bool ansinv = false;
bool cinv;
void solve() {
  for (int iter = 0; iter < 24; ++iter) {
    int cur = 0;
    next_permutation(st.begin(), st.end());
    for (int j = 0; j < n; ++j) {
      int p = (j % 2) * 2;
      int cv = N;
      array<int, 2> cl{};
      string str[2];
      for (int l = 0; l < 2; ++l) {
        for (int i = 0; i < m; ++i) {
          char ch = st[p + (l ^ (i & 1))];
          str[l].push_back(ch);
          cl[l] += s[j][i] != str[l][i];
        }
      }
      if (cl[0] < cl[1]) {
        curr[j] = str[0];
        cur += cl[0];
      } else {
        curr[j] = str[1];
        cur += cl[1];
      }
    }
    if (ans > cur) {
      copy(curr, curr + n, best);
      ansinv = cinv;
      ans = cur;
    }
  }
}
void invert(decltype(t) s) {
  for (int i = 0; i < m; ++i) {
    t[i] = "";
    t[i].reserve(n);
    for (int j = 0; j < n; ++j) {
      t[i] += s[j][i];
    }
  }
  copy(t, t + m, s);
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  cout.setf(ios::fixed);
  cout.precision(20);
  cin >> n >> m;
  for (int i = 0; i < n; ++i) {
    cin >> s[i];
  }
  solve();
  invert(s);
  swap(n, m);
  cinv = true;
  solve();
  if (ansinv) {
    invert(best);
  }
  swap(n, m);
  for (int i = 0; i < n; ++i) {
    cout << best[i] << "\n";
  }
  cerr << ans << "\n";
}
