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 ll = int64_t;
auto& errStream = cerr;
class CerrDummy {
} cerrDummy;
template <class T>
CerrDummy& operator<<(CerrDummy& cd, const T&) {
  return cd;
}
using charTDummy = char;
using traitsDummy = char_traits<charTDummy>;
CerrDummy& operator<<(CerrDummy& cd,
                      basic_ostream<charTDummy, traitsDummy>&(
                          basic_ostream<charTDummy, traitsDummy>&)) {
  return cd;
}
using pi = pair<ll, ll>;
using vi = vector<ll>;
using ld = long double;
template <class T, class U>
ostream& operator<<(ostream& os, const pair<T, U>& p) {
  os << "(" << p.first << "," << p.second << ")";
  return os;
}
template <class T>
ostream& operator<<(ostream& os, const vector<T>& v) {
  os << "{";
  for (ll i = ll(0); i < ll((ll)v.size()); i++) {
    if (i) os << ",";
    os << v[i];
  }
  os << "}";
  return os;
}
ll read() {
  ll i;
  scanf("%" SCNd64, &i);
  return i;
}
void printSpace() { printf(" "); }
void printEoln() { printf("\n"); }
void print(ll x, ll suc = 1) {
  printf("%" PRId64, x);
  if (suc == 1) printEoln();
  if (suc == 2) printSpace();
}
string readString() {
  static char buf[3341000];
  scanf("%s", buf);
  return string(buf);
}
char* readCharArray() {
  static char buf[3341000];
  static ll bufUsed = 0;
  char* ret = buf + bufUsed;
  scanf("%s", ret);
  bufUsed += strlen(ret) + 1;
  return ret;
}
template <class T, class U>
void chmax(T& a, U b) {
  if (a < b) a = b;
}
template <class T, class U>
void chmin(T& a, U b) {
  if (b < a) a = b;
}
template <class T>
T Sq(const T& t) {
  return t * t;
}
void Yes(bool ex = true) {
  cout << "YES" << endl;
  if (ex) exit(0);
}
void No(bool ex = true) {
  cout << "NO" << endl;
  if (ex) exit(0);
}
const ll infLL = LLONG_MAX / 3;
const ll inf = infLL;
vector<string> flip(vector<string> x) {
  ll n = x.size(), m = x[0].size();
  vector<string> res(m, string(n, '.'));
  for (ll i = ll(0); i < ll(m); i++)
    for (ll j = ll(0); j < ll(n); j++) res[i][j] = x[j][i];
  return res;
}
pair<ll, vector<string>> Solve(vector<string> x) {
  ll n = x.size(), m = x[0].size();
  string waf = "ACGT";
  sort(waf.begin(), waf.end());
  pair<ll, string> ans(inf, "");
  do {
    if (waf[0] < waf[1] && waf[2] < waf[3]) {
      ll sum = 0;
      for (ll i = ll(0); i < ll(n); i++) {
        ll k = (i % 2) * 2;
        ll mn = inf;
        for (ll _ = ll(0); _ < ll(2); _++) {
          ll cnt = 0;
          for (ll j = ll(0); j < ll(m); j++)
            if (x[i][j] != waf[k + j % 2]) cnt++;
          chmin(mn, cnt);
          swap(waf[k], waf[k + 1]);
        }
        sum += mn;
      }
      chmin(ans, make_pair(sum, waf));
    }
  } while (next_permutation(waf.begin(), waf.end()));
  waf = ans.second;
  vector<string> res(n, string(m, '.'));
  for (ll i = ll(0); i < ll(n); i++) {
    ll k = (i % 2) * 2;
    pi mn(inf, -1);
    for (ll _ = ll(0); _ < ll(2); _++) {
      ll cnt = 0;
      for (ll j = ll(0); j < ll(m); j++)
        if (x[i][j] != waf[k + j % 2]) cnt++;
      chmin(mn, pi(cnt, _));
      swap(waf[k], waf[k + 1]);
    }
    if (mn.second) swap(waf[k], waf[k + 1]);
    for (ll j = ll(0); j < ll(m); j++) res[i][j] = waf[k + j % 2];
  }
  return make_pair(ans.first, res);
}
signed main() {
  ll n = read(), m = read();
  vector<string> x(n);
  for (ll i = ll(0); i < ll(n); i++) {
    x[i] = readString();
  }
  auto ans1 = Solve(x);
  auto ans2 = Solve(flip(x));
  ans2.second = flip(ans2.second);
  auto ans = min(ans1, ans2);
  {
    ll dif = 0;
    for (ll i = ll(0); i < ll(n); i++)
      for (ll j = ll(0); j < ll(m); j++)
        if (x[i][j] != ans.second[i][j]) dif++;
    assert(dif == ans.first);
    cerrDummy << dif << endl;
  }
  for (ll i = ll(0); i < ll(n); i++) printf("%s\n", ans.second[i].c_str());
}
