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;
vector<char> chars = {'A', 'C', 'G', 'T'};
vector<string> inp;
int n, m;
pair<int, vector<string>> solve(vector<string> s) {
  pair<int, vector<string>> ans;
  ans.first = (1 << 30);
  for (char aa : chars) {
    for (char bb : chars) {
      char a = aa, b = bb;
      if (a >= b) continue;
      char c, d;
      for (char cc : chars)
        if (cc != a && cc != b) c = cc;
      for (char cc : chars)
        if (cc != a && cc != b && cc != c) d = cc;
      int diffs = 0;
      vector<string> res(s.size());
      for (int i = 0; i < s.size(); i += 2) {
        int abcost = 0, bacost = 0;
        for (int j = 0; j < s[i].size(); j++) {
          if (j % 2 == 0) {
            if (s[i][j] != a) abcost++;
            if (s[i][j] != b) bacost++;
          } else {
            if (s[i][j] != a) bacost++;
            if (s[i][j] != b) abcost++;
          }
        }
        if (abcost < bacost) {
          for (int j = 0; j < s[i].size(); j++) {
            res[i] += (j % 2 ? b : a);
          }
        } else {
          for (int j = 0; j < s[i].size(); j++) {
            res[i] += (j % 2 ? a : b);
          }
        }
        diffs += min(abcost, bacost);
      }
      a = c;
      b = d;
      for (int i = 1; i < s.size(); i += 2) {
        int abcost = 0, bacost = 0;
        for (int j = 0; j < s[i].size(); j++) {
          if (j % 2 == 0) {
            if (s[i][j] != a) abcost++;
            if (s[i][j] != b) bacost++;
          } else {
            if (s[i][j] != a) bacost++;
            if (s[i][j] != b) abcost++;
          }
        }
        if (abcost < bacost) {
          for (int j = 0; j < s[i].size(); j++) {
            res[i] += (j % 2 ? b : a);
          }
        } else {
          for (int j = 0; j < s[i].size(); j++) {
            res[i] += (j % 2 ? a : b);
          }
        }
        diffs += min(abcost, bacost);
      }
      ans = min(ans, {diffs, res});
    }
  }
  return ans;
}
vector<string> invert(vector<string> s) {
  vector<string> res(s[0].size());
  for (int i = 0; i < s.size(); i++) {
    for (int j = 0; j < s[i].size(); j++) {
      res[j].push_back(s[i][j]);
    }
  }
  return res;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> m;
  for (int i = 0; i < n; i++) {
    string in;
    cin >> in;
    inp.push_back(in);
  }
  assert(invert(invert(inp)) == inp);
  pair<int, vector<string>> res = solve(inp);
  inp = invert(inp);
  pair<int, vector<string>> res2 = solve(inp);
  vector<string> ans = res.second;
  if (res2.first < res.first) {
    ans = invert(res2.second);
  }
  assert(n == ans.size());
  for (int i = 0; i < ans.size(); i++) {
    cout << ans[i] << "\n";
  }
  cerr << min(res2.first, res.first) << endl;
}
