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;
int n, m;
vector<string> tab, rev;
unordered_map<string, string> inv;
inline string inversePattern(string pattern) {
  if (inv.count(pattern)) return inv[pattern];
  string ans = "ACTG";
  ans.erase(ans.find(pattern[0]), 1);
  ans.erase(ans.find(pattern[1]), 1);
  return inv[pattern] = ans;
}
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cin >> n >> m;
  tab.resize(n);
  for (auto& row : tab) cin >> row;
  rev.resize(m);
  for (int i = 0; i < m; ++i) {
    rev[i].resize(n);
    for (int j = 0; j < n; ++j) rev[i][j] = tab[j][i];
  }
  int ans = 333333;
  vector<bool> R;
  string pattern;
  bool mode = false;
  bool optimal = false;
  for (string pat : {"AC", "AG", "AT", "CG", "CT", "GT"}) {
    for (auto table : {tab, rev}) {
      string tmp = pat;
      mode = !mode;
      int diff = 0;
      vector<bool> r;
      for (auto row : table) {
        int r1 = 0, r2 = 0;
        for (int i = 0; i < (int)row.length(); ++i) {
          if (row[i] != tmp[i & 1]) ++r1;
          if (row[i] != tmp[~i & 1]) ++r2;
        }
        diff += min(r1, r2);
        r.push_back(r1 > r2);
        tmp = inversePattern(tmp);
      }
      if (diff < ans) {
        ans = diff;
        R = move(r);
        pattern = pat;
        optimal = mode;
      }
    }
  }
  if (optimal) {
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < m; ++j) {
        tab[i][j] = pattern[(j & 1) ^ R[i]];
      }
      pattern = inversePattern(pattern);
    }
  } else {
    for (int j = 0; j < m; ++j) {
      for (int i = 0; i < n; ++i) {
        tab[i][j] = pattern[(i & 1) ^ R[j]];
      }
      pattern = inversePattern(pattern);
    }
  }
  for (auto row : tab) {
    for (auto cell : row) {
      cout << cell;
    }
    cout << '\n';
  }
}
