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 main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int n, m;
  cin >> n >> m;
  vector<vector<int>> table(n, vector<int>(m));
  for (int i = 0; i < n; i++) {
    string str;
    cin >> str;
    for (int j = 0; j < m; j++) {
      if (str[j] == 'A') {
        table[i][j] = 0;
      } else if (str[j] == 'G') {
        table[i][j] = 1;
      } else if (str[j] == 'C') {
        table[i][j] = 2;
      } else {
        table[i][j] = 3;
      }
    }
  }
  vector<int> gu(2), ki(2);
  long long ecost = 1LL << 60, fcost = 1LL << 60;
  vector<int> gug(2), kik(2), ccc(n), cccc(n);
  vector<int> gugg(2), kikk(2), ddd(m), dddd(m);
  for (int i = 0; i < 4; i++) {
    for (int j = i + 1; j < 4; j++) {
      if (i == j) continue;
      gu[0] = i, gu[1] = j;
      int k = 0, l = 0;
      for (; k == i || k == j; k++) {
      }
      for (; l == i || l == j || l == k; l++) {
      }
      ki[0] = k, ki[1] = l;
      long long dcost = 0;
      for (int a = 0; a < n; a++) {
        long long mincost = 1LL << 60;
        for (int c = 0; c < 2; c++) {
          long long ccost = 0;
          for (int b = 0; b < m; b++)
            if (a % 2 == 0) {
              if (table[a][b] != gu[(b + c) % 2]) {
                ccost++;
              }
            } else {
              if (table[a][b] != ki[(b + c) % 2]) {
                ccost++;
              }
            }
          if (mincost > ccost) {
            ccc[a] = c;
          }
          mincost = min(mincost, ccost);
        }
        dcost += mincost;
      }
      if (ecost > dcost) {
        gug = gu;
        kik = ki;
        ecost = dcost;
        cccc = ccc;
      }
      long long gcost = 0;
      for (int a = 0; a < m; a++) {
        long long mincost = 1LL << 60;
        for (int c = 0; c < 2; c++) {
          long long ccost = 0;
          for (int b = 0; b < n; b++)
            if (a % 2 == 0) {
              if (table[b][a] != gu[(b + c) % 2]) {
                ccost++;
              }
            } else {
              if (table[b][a] != ki[(b + c) % 2]) {
                ccost++;
              }
            }
          if (mincost > ccost) {
            ddd[a] = c;
          }
          mincost = min(mincost, ccost);
        }
        gcost += mincost;
      }
      if (fcost > gcost) {
        gugg = gu;
        kikk = ki;
        fcost = gcost;
        dddd = ddd;
      }
    }
  }
  vector<char> tai(4);
  tai[0] = 'A';
  tai[1] = 'G';
  tai[2] = 'C';
  tai[3] = 'T';
  if (ecost < fcost) {
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        if (i % 2 == 0) {
          cout << tai[gug[(j + cccc[i]) % 2]];
        } else {
          cout << tai[kik[(j + cccc[i]) % 2]];
        }
      }
      cout << "\n";
    }
  } else {
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        if (j % 2 == 0) {
          cout << tai[gugg[(i + dddd[j]) % 2]];
        } else {
          cout << tai[kikk[(i + dddd[j]) % 2]];
        }
      }
      cout << "\n";
    }
  }
  return 0;
}
