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;
struct _IO {
  _IO() {
    ios::sync_with_stdio(0);
    cin.tie(0);
  }
} _io;
void uni(vector<int> &v) {
  sort(v.begin(), v.end());
  v.erase(unique(v.begin(), v.end()), v.end());
}
long double rd() {
  long double x;
  cin >> x;
  return x;
}
long long ri() {
  long long x;
  cin >> x;
  return x;
}
string rs() {
  string s;
  cin >> s;
  return s;
}
pair<int, int> rpi() {
  pair<int, int> x;
  cin >> x.first >> x.second;
  return x;
}
vector<int> rvi(int n, int f = 0) {
  vector<int> v(n + f);
  for (int i = f; i < v.size(); i++) cin >> v[i];
  return v;
}
vector<vector<int>> rvii(int n, int m, int f = 0) {
  vector<vector<int>> v(n + f, vector<int>(n + f));
  for (int i = f; i < v.size(); i++)
    for (int j = f; j < v[0].size(); j++) cin >> v[i][j];
  return v;
}
void pr(){};
template <class T, class... U>
void pr(T x, U... y) {
  cout << x << ' ', pr(y...);
}
void prl() { cout << '\n'; };
template <class T, class... U>
void prl(T x, U... y) {
  cout << x << ' ', prl(y...);
}
void pr(const vector<int> &v, int f = 0) {
  for (int i = f; i < v.size(); i++) cout << v[i] << ' ';
}
void prl(const vector<int> &v, int f = 0) {
  pr(v, f);
  cout << '\n';
}
void pr(const pair<int, int> &x) { cout << x.first << ' ' << x.second; };
void prl(const pair<int, int> &x) {
  pr(x);
  cout << '\n';
}
const int N = 2e5 + 5, M = 1e9 + 7;
int dp[N][16], lst[N][16];
pair<int, vector<string>> solve(int n, int m, vector<string> vs) {
  vector<int> sta;
  for (int i = 0; i < 4; i++) {
    for (int j = 0; j < 4; j++) {
      if (i != j) sta.push_back(i * 10 + j);
    }
  }
  string t = "ATCG";
  for (int i = 0; i < m; i++) {
    for (int s = 0; s < sta.size(); s++) {
      dp[i + 1][s] = n * m, lst[i + 1][s] = -1;
      int mask = sta[s], x = 0;
      string p;
      p.push_back(t[mask / 10]);
      p.push_back(t[mask % 10]);
      for (int j = 0; j < n; j++) {
        x += vs[j][i] != p[j % 2];
      }
      for (int ls = 0; ls < sta.size(); ls++) {
        int u = sta[ls] / 10, v = sta[ls] % 10;
        if (u == mask / 10 || u == mask % 10 || v == mask / 10 ||
            v == mask % 10)
          continue;
        if (dp[i + 1][s] > dp[i][ls] + x) {
          dp[i + 1][s] = dp[i][ls] + x;
          lst[i + 1][s] = ls;
        }
      }
    }
  }
  vector<int> ans;
  int cur = 0, ansi = 0;
  for (int i = 0; i < sta.size(); i++) {
    if (dp[m][i] < dp[m][cur]) cur = i;
  }
  ansi = cur;
  for (int i = m; i >= 1; i--) {
    ans.push_back(sta[cur]);
    cur = lst[i][cur];
  }
  reverse(ans.begin(), ans.end());
  vector<string> ans2(n);
  for (int j = 0; j < m; j++) {
    for (int i = 0; i < n; i++) {
      string p;
      p.push_back(t[ans[j] / 10]);
      p.push_back(t[ans[j] % 10]);
      ans2[i].push_back(p[i % 2]);
    }
  }
  return make_pair(dp[m][ansi], ans2);
}
int main() {
  int n = ri(), m = ri();
  vector<string> vs(n);
  for (int i = 0; i < n; i++) vs[i] = rs();
  auto ans1 = solve(n, m, vs);
  {
    vector<string> tmp(m);
    for (int j = 0; j < m; j++)
      for (int i = 0; i < n; i++) tmp[j].push_back(vs[i][j]);
    swap(vs, tmp);
    swap(n, m);
  }
  auto ans2 = solve(n, m, vs);
  {
    vector<string> tmp(m);
    for (int j = 0; j < m; j++)
      for (int i = 0; i < n; i++) tmp[j].push_back(ans2.second[i][j]);
    swap(ans2.second, tmp);
    swap(n, m);
  }
  for (int i = 0; i < n; i++)
    prl(ans1.first < ans2.first ? ans1.second[i] : ans2.second[i]);
}
