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>
#pragma comment(linker, "/STACK:256000000")
using namespace std;
const int INF = (int)(1e9 + 1e5);
const long long LINF = (long long)(2e18);
const long long BASE = 1003;
const double EPS = 1e-9;
const int MOD = 1000000007;
int tnum;
struct filling {
  bool vert;
  string pattern;
};
int n, m;
vector<string> f;
vector<string> ans;
void init() {
  cin >> n >> m;
  f.resize(n);
  for (int i = 0; i < n; ++i) {
    cin >> f[i];
  }
}
int get_row_fixed(int num, const string& pat) {
  int res = 0;
  for (int i = 0; i < m; ++i) {
    res += (f[num][i] != pat[i & 1]);
    ans[num][i] = pat[i & 1];
  }
  return res;
}
int get_row(int num, const string& pat) {
  auto rev_pat = pat;
  std::reverse(rev_pat.begin(), rev_pat.end());
  auto res = get_row_fixed(num, pat);
  auto res_rev = get_row_fixed(num, rev_pat);
  if (res < res_rev) {
    get_row_fixed(num, pat);
  }
  return min(res, res_rev);
}
int get_column_fixed(int num, const string& pat) {
  int res = 0;
  for (int i = 0; i < n; ++i) {
    res += (f[i][num] != pat[i & 1]);
    ans[i][num] = pat[i & 1];
  }
  return res;
}
int get_column(int num, const string& pat) {
  auto rev_pat = pat;
  std::reverse(rev_pat.begin(), rev_pat.end());
  auto res = get_column_fixed(num, pat);
  auto res_rev = get_column_fixed(num, rev_pat);
  if (res < res_rev) {
    get_column_fixed(num, pat);
  }
  return min(res, res_rev);
}
int try_fill(filling fil) {
  int res = 0;
  auto first = fil.pattern.substr(0, 2);
  auto second = fil.pattern.substr(2, 2);
  if (fil.vert) {
    for (int i = 0; i < m; ++i) {
      res += get_column(i, (i & 1) ? second : first);
    }
  } else {
    for (int i = 0; i < n; ++i) {
      res += get_row(i, (i & 1) ? second : first);
    }
  }
  return res;
}
void solve() {
  ans.resize(n);
  for (int i = 0; i < n; ++i) {
    ans[i].resize(m);
  }
  filling cur, best;
  int best_res = INF;
  for (int vert = 0; vert <= 1; ++vert) {
    cur.pattern = "ACGT";
    cur.vert = vert;
    unordered_set<string> was;
    do {
      auto str = cur.pattern.substr(0, 2);
      if (str[0] > str[1]) {
        swap(str[0], str[1]);
      }
      if (was.count(str)) {
        continue;
      }
      auto cur_res = try_fill(cur);
      if (cur_res < best_res) {
        best_res = cur_res;
        best = cur;
      }
      was.insert(str);
    } while (next_permutation(cur.pattern.begin(), cur.pattern.end()));
  }
  try_fill(best);
}
void print_answer() {
  for (int i = 0; i < n; ++i) {
    cout << ans[i] << "\n";
  }
}
void precalc() {}
void run() {
  precalc();
  int t = 1;
  for (tnum = 1; tnum <= t; ++tnum) {
    init();
    solve();
    print_answer();
  }
}
int main() {
  srand(90);
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  run();
  return 0;
}
