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 namespace std::chrono;
long long fexp(long long a, long long b, long long m) {
  long long ans = 1;
  while (b) {
    if (b & 1) ans = ans * a % m;
    b /= 2;
    a = a * a % m;
  }
  return ans;
}
long long inverse(long long a, long long p) { return fexp(a, p - 2, p); }
long long fac[300005];
long long ncr(long long n, long long r, long long p) {
  if (r == 0) return 1;
  return (fac[n] * inverse(fac[r], p) % p * inverse(fac[n - r], p) % p) % p;
}
bool sortby(pair<pair<long long, long long>, long long> &a,
            pair<pair<long long, long long>, long long> &b) {
  if (a.first.first == b.first.first) return (a.first.second < b.first.second);
  return (a.first.first < b.first.first);
  if (a.second == b.second) return (a.first < b.first);
  return (a.second < b.second);
}
long long n, m, sum = 3000000;
vector<string> ans;
void fun(vector<string> &c, string x, string y) {
  vector<string> s;
  long long temp = 0;
  string t, tt, qt, qtt;
  for (long long j = 0; j < m / 2; j++) t.push_back(x[0]), t.push_back(x[1]);
  if (m & 1) t.push_back(x[0]);
  if (m & 1) tt.push_back(x[1]);
  for (long long j = 0; j < m / 2; j++) tt.push_back(x[0]), tt.push_back(x[1]);
  reverse((tt).begin(), (tt).end());
  for (long long j = 0; j < m / 2; j++) qt.push_back(y[0]), qt.push_back(y[1]);
  if (m & 1) qt.push_back(y[0]);
  if (m & 1) qtt.push_back(y[1]);
  for (long long j = 0; j < m / 2; j++)
    qtt.push_back(y[0]), qtt.push_back(y[1]);
  reverse((qtt).begin(), (qtt).end());
  for (long long i = 0; i < n; i++) {
    long long a = 0, b = 0;
    for (long long j = 0; j < m; j++) {
      if (i & 1 ^ 1) {
        if (c[i][j] != t[j]) a++;
        if (c[i][j] != tt[j]) b++;
      } else {
        if (c[i][j] != qt[j]) a++;
        if (c[i][j] != qtt[j]) b++;
      }
    }
    if (i & 1 ^ 1) {
      if (a < b)
        s.push_back(t);
      else
        s.push_back(tt);
    } else {
      if (a < b)
        s.push_back(qt);
      else
        s.push_back(qtt);
    }
    temp += (min(a, b));
  }
  if (temp < sum) {
    sum = temp;
    if ((long long)ans.size() == 0)
      for (long long i = 0; i < n; i++) ans.push_back(s[i]);
    for (long long i = 0; i < n; i++) ans[i] = s[i];
  }
  s.clear();
  temp = 0;
  t.clear();
  tt.clear();
  qt.clear();
  qtt.clear();
  for (long long j = 0; j < n / 2; j++) t.push_back(x[0]), t.push_back(x[1]);
  if (n & 1) t.push_back(x[0]);
  if (n & 1) tt.push_back(x[1]);
  for (long long j = 0; j < n / 2; j++) tt.push_back(x[0]), tt.push_back(x[1]);
  reverse((tt).begin(), (tt).end());
  for (long long j = 0; j < n / 2; j++) qt.push_back(y[0]), qt.push_back(y[1]);
  if (n & 1) qt.push_back(y[0]);
  if (n & 1) qtt.push_back(y[1]);
  for (long long j = 0; j < n / 2; j++)
    qtt.push_back(y[0]), qtt.push_back(y[1]);
  reverse((qtt).begin(), (qtt).end());
  for (long long j = 0; j < m; j++) {
    long long a = 0, b = 0;
    for (long long i = 0; i < n; i++) {
      if (j & 1 ^ 1) {
        if (c[i][j] != t[i]) a++;
        if (c[i][j] != tt[i]) b++;
      } else {
        if (c[i][j] != qt[i]) a++;
        if (c[i][j] != qtt[i]) b++;
      }
    }
    if (j & 1 ^ 1) {
      if (a < b)
        s.push_back(t);
      else
        s.push_back(tt);
    } else {
      if (a < b)
        s.push_back(qt);
      else
        s.push_back(qtt);
    }
    temp += (min(a, b));
  }
  if (temp < sum) {
    sum = temp;
    for (long long i = 0; i < n; i++)
      for (long long j = 0; j < m; j++) ans[i][j] = s[j][i];
  }
}
long long solve() {
  cin >> n >> m;
  vector<string> c(n);
  for (long long i = 0; i < n; i++) cin >> c[i];
  string s = "ACGT";
  fun(c, "AC", "GT");
  fun(c, "AG", "CT");
  fun(c, "AT", "CG");
  fun(c, "CG", "AT");
  fun(c, "CT", "AG");
  fun(c, "GT", "AC");
  for (long long i = 0; i < n; i++) cout << ans[i] << "\n";
  return 0;
}
signed main() {
  auto start = high_resolution_clock::now();
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  ;
  long long t = 1;
  while (t--) {
    solve();
    cout << "\n";
  }
  auto stop = high_resolution_clock::now();
  auto duration = duration_cast<microseconds>(stop - start);
  cerr << "Time taken:" << duration.count() / 1000000.0 << "seconds"
       << "\n";
  return 0;
}
