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;
const char* const TG[] = {"ACGT", "AGCT", "ATCG", "CGAT", "CTAG", "GTAC"};
int topChg = INT_MAX;
vector<string> topGd;
void sv(vector<string> const& gd) {
  int N = ((int)(gd).size()), M = ((int)(gd[0]).size());
  topChg = INT_MAX;
  topGd.clear();
  for (int a = 0; a < int(6); a++) {
    vector<string> newGd(N);
    int ochg = 0;
    for (int n = 0; n < int(N); n++) {
      int bestChg = INT_MAX;
      for (int o = 0; o < int(2); o++) {
        int chg = 0;
        string tr = gd[n];
        for (int m = 0; m < int(M); m++) {
          char ec = TG[a][2 * (n % 2) + (m + o) % 2];
          if (ec != tr[m]) {
            tr[m] = ec;
            ++chg;
          }
        }
        if (chg < bestChg) {
          bestChg = chg;
          newGd[n] = move(tr);
        }
      }
      ochg += bestChg;
    }
    if (ochg < topChg) {
      topChg = ochg;
      topGd = move(newGd);
    }
  }
}
vector<string> flipIt(vector<string> const& gd) {
  int N = ((int)(gd).size()), M = ((int)(gd[0]).size());
  vector<string> newGd(M, string(N, '\0'));
  for (int n = 0; n < int(N); n++)
    for (int m = 0; m < int(M); m++) newGd[m][n] = gd[n][m];
  return newGd;
}
int main() {
  int N, M;
  scanf("%d%d", &N, &M);
  vector<string> gd(N, string(M, '\0'));
  char tmp[300001];
  for (int n = 0; n < int(N); n++) {
    scanf(" %s", tmp);
    memcpy(&gd[n][0], tmp, M);
  }
  sv(gd);
  int chg = topChg;
  vector<string> ngd = topGd;
  sv(flipIt(gd));
  if (topChg < chg) {
    chg = topChg;
    ngd = flipIt(topGd);
  }
  for (int n = 0; n < int(N); n++) {
    puts(ngd[n].c_str());
  }
}
