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;
using LL = long long;
using PII = pair<int, int>;
const string S = "AGCT";
vector<string> s, s1, s2;
vector<string> flip(vector<string> s) {
  vector<string> res;
  int n = s.size(), m = s[0].length();
  res.resize(m);
  for (int i = 0; i < m; i++) {
    res[i].resize(n);
    for (int j = 0; j < n; j++) res[i][j] = s[j][i];
  }
  return res;
}
int calc(vector<string> s, vector<string> &ans) {
  int n = s.size(), m = s[0].length();
  ans = s;
  int bestCnt = INT_MAX;
  for (int i = 0; i < 4; i++)
    for (int j = i + 1; j < 4; j++) {
      int k = 0;
      while (k == i || k == j) k++;
      int l = 6 - (i + j + k);
      vector<int> a = {i, j, k, l};
      vector<string> cur = s;
      int cnt = 0;
      for (int x = 0; x < n; x++) {
        int c1 = 0, c2 = 0;
        for (int y = 0; y < m; y++) {
          c1 += S[a[((x & 1) << 1) + (y & 1)]] != s[x][y];
          c2 += S[a[((x & 1) << 1) + ((y & 1) ^ 1)]] != s[x][y];
        }
        int inv = c2 < c1;
        for (int y = 0; y < m; y++)
          cur[x][y] = S[a[((x & 1) << 1) + ((y & 1) ^ inv)]];
        cnt += min(c1, c2);
      }
      if (cnt < bestCnt) {
        ans = cur;
        bestCnt = cnt;
      }
    }
  return bestCnt;
}
int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  for (int i = 0; i < n; i++) {
    string ss;
    cin >> ss;
    s.emplace_back(ss);
  }
  int a1, a2;
  a1 = calc(s, s1);
  a2 = calc(flip(s), s2);
  s2 = flip(s2);
  if (a1 > a2) s1 = s2;
  for (auto ss : s1) cout << ss << '\n';
  return 0;
}
