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 cmp_str(string &a, string &b) {
  int s = 0;
  for (int i = 0; i < a.size(); i++) s += (a[i] == b[i]);
  return s;
}
string gen_str(int s, char a, char b) {
  string res = "";
  for (int i = 0; i < s; i++)
    if (i % 2 == 1)
      res += b;
    else
      res += a;
  return res;
}
int solve(vector<string> &src, string pat, vector<string> &ans) {
  ans.clear();
  int res = 0;
  string a1 = gen_str(src[0].size(), pat[0], pat[1]);
  string a2 = gen_str(src[0].size(), pat[1], pat[0]);
  string b1 = gen_str(src[0].size(), pat[2], pat[3]);
  string b2 = gen_str(src[0].size(), pat[3], pat[2]);
  for (int i = 0; i < src.size(); i++) {
    if (i % 2 == 0) {
      int x1 = cmp_str(src[i], a1);
      int x2 = cmp_str(src[i], a2);
      if (x1 > x2)
        ans.push_back(a1);
      else
        ans.push_back(a2);
      res += max(x1, x2);
    } else {
      int x1 = cmp_str(src[i], b1);
      int x2 = cmp_str(src[i], b2);
      if (x1 > x2)
        ans.push_back(b1);
      else
        ans.push_back(b2);
      res += max(x1, x2);
    }
  }
  return res;
}
void trans(vector<string> &A, vector<string> &B) {
  B.clear();
  B.resize(A[0].size(), "");
  for (int i = 0; i < A.size(); i++)
    for (int j = 0; j < A[i].size(); j++) B[j] += A[i][j];
}
int main() {
  int n, m;
  cin >> n >> m;
  vector<string> A(n), B, C, D;
  for (int i = 0; i < n; i++) cin >> A[i];
  trans(A, D);
  vector<string> st = {"AGCT", "ACGT", "ATCG", "GCAT", "GTAC", "CTAG"};
  int best = 0;
  for (int i = 0; i < 6; i++) {
    int r = solve(A, st[i], B);
    if (r > best) {
      best = r;
      swap(C, B);
    }
    r = solve(D, st[i], B);
    if (r > best) {
      best = r;
      trans(B, C);
    }
  }
  for (int i = 0; i < n; i++) cout << C[i] << '\n';
  return 0;
}
