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;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
inline void setin(string s) { freopen(s.c_str(), "r", stdin); }
inline void setout(string s) { freopen(s.c_str(), "w", stdout); }
template <typename T>
inline T range(T l, T r) {
  return uniform_int_distribution<T>(l, r)(rng);
}
template <typename T>
void Min(T &a, T b) {
  a = min(a, b);
}
template <typename T>
void Max(T &a, T b) {
  a = max(a, b);
}
const int inf = 2e9;
const int mod = 1e9 + 7;
const int N = 3e5 + 15;
int n, m;
inline char rev_gt(int x) {
  if (x == 1) return 'A';
  if (x == 2) return 'T';
  if (x == 3) return 'G';
  return 'C';
}
inline int gt(char c) {
  if (c == 'A') return 1;
  if (c == 'T') return 2;
  if (c == 'G') return 3;
  return 4;
}
vector<vector<int>> ans, a, b;
int val = inf;
bool flag;
vector<vector<int>> transpose(const vector<vector<int>> &a) {
  vector<vector<int>> nw(a[0].size(), vector<int>(a.size(), 0));
  for (int i = 0; i < a.size(); ++i)
    for (int j = 0; j < a[i].size(); ++j) nw[j][i] = a[i][j];
  return nw;
}
void solve(bool rev = false) {
  vector<int> ord = {1, 2, 3, 4};
  do {
    b[1][1] = ord[0], b[1][2] = ord[1], b[2][1] = ord[2], b[2][2] = ord[3];
    for (int i = 3; i <= n; ++i)
      for (int j = 1; j <= 2; ++j) b[i][j] = b[i - 2][j];
    for (int j = 3; j <= m; ++j) {
      pair<int, int> val(0, 0);
      vector<int> is = {};
      if (j & 1)
        is = {ord[0], ord[2]};
      else
        is = {ord[1], ord[3]};
      for (int i = 1; i <= n; ++i) {
        val.first += is[i & 1] != a[i][j];
        val.second += is[(i & 1) ^ 1] != a[i][j];
      }
      for (int i = 1; i <= n; ++i)
        b[i][j] = (val.first < val.second ? is[i & 1] : is[(i & 1) ^ 1]);
    }
    int cur = 0;
    for (int i = 1; i <= n; ++i)
      for (int j = 1; j <= m; ++j) cur += a[i][j] != b[i][j];
    if (cur < val) ans = b, val = cur, flag = rev;
  } while (next_permutation(ord.begin(), ord.end()));
}
int main() {
  scanf("%d %d\n", &n, &m);
  a = vector<vector<int>>(n + 5, vector<int>(m + 5, 0));
  b = a;
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= m; ++j) {
      char c = getchar();
      a[i][j] = gt(c);
    }
    getchar();
  }
  solve();
  a = transpose(a);
  swap(n, m);
  b = a;
  solve(true);
  assert(!ans.empty());
  if (flag) ans = transpose(ans);
  swap(n, m);
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= m; ++j) putchar(rev_gt(ans[i][j]));
    puts("");
  }
  return 0;
}
