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 letters[] = {'A', 'G', 'C', 'T'};
const int NMAX = 3e5 + 5;
int N, M;
int A, G, C, T;
int best;
vector<vector<int> > a, b;
vector<int> prm, bestprm;
int fqlin[NMAX][2][4], fqcol[NMAX][2][4];
char gletter() {
  char ch = getchar();
  while (ch < 'A' || 'Z' < ch) ch = getchar();
  return ch;
}
int main() {
  scanf("%d%d\n", &N, &M);
  a.resize(N + 1);
  for (int i = 1; i <= N; i++) {
    a[i].resize(M + 1);
    for (int j = 1; j <= M; j++) {
      char ch = gletter();
      if (ch == 'A')
        a[i][j] = 0;
      else if (ch == 'G')
        a[i][j] = 1;
      else if (ch == 'C')
        a[i][j] = 2;
      else if (ch == 'T')
        a[i][j] = 3;
      fqlin[i][j % 2][a[i][j]]++;
      fqcol[j][i % 2][a[i][j]]++;
    }
  }
  best = -1;
  int who = -1;
  for (int i = 0; i < 4; i++) prm.push_back(i);
  do {
    {
      int cost = 0;
      A = prm[0], G = prm[1], C = prm[2], T = prm[3];
      cost += fqcol[1][1][A] + fqcol[1][0][C] + fqcol[2][1][G] + fqcol[2][0][T];
      for (int i = 3; i <= M; i++) {
        if (i % 2 == 0)
          cost += max(fqcol[i][1][G] + fqcol[i][0][T],
                      fqcol[i][0][G] + fqcol[i][1][T]);
        else
          cost += max(fqcol[i][1][A] + fqcol[i][0][C],
                      fqcol[i][0][A] + fqcol[i][1][C]);
      }
      if (cost > best) {
        best = cost;
        bestprm = prm;
        who = 0;
      }
    }
    {
      int cost = 0;
      A = prm[0], G = prm[1], C = prm[2], T = prm[3];
      cost += fqlin[1][1][A] + fqlin[2][1][C] + fqlin[1][0][G] + fqlin[2][0][T];
      for (int i = 3; i <= N; i++) {
        if (i % 2 == 0)
          cost += max(fqlin[i][1][C] + fqlin[i][0][T],
                      fqlin[i][0][C] + fqlin[i][1][T]);
        else
          cost += max(fqlin[i][1][A] + fqlin[i][0][G],
                      fqlin[i][0][A] + fqlin[i][1][G]);
      }
      if (cost > best) {
        best = cost;
        bestprm = prm;
        who = 1;
      }
    }
  } while (next_permutation(prm.begin(), prm.end()));
  b = a;
  prm = bestprm;
  if (who == 0) {
    A = prm[0], G = prm[1], C = prm[2], T = prm[3];
    b[1][1] = A, b[2][1] = C, b[1][2] = G, b[2][2] = T;
    for (int i = 3; i <= M; i++) {
      if (i % 2 == 1) {
        if (fqcol[i][1][A] + fqcol[i][0][C] > fqcol[i][0][A] + fqcol[i][1][C])
          b[1][i] = A, b[2][i] = C;
        else
          b[1][i] = C, b[2][i] = A;
      } else {
        if (fqcol[i][1][G] + fqcol[i][0][T] > fqcol[i][0][G] + fqcol[i][1][T])
          b[1][i] = G, b[2][i] = T;
        else
          b[1][i] = T, b[2][i] = G;
      }
    }
    for (int i = 3; i <= N; i++)
      for (int j = 1; j <= M; j++) b[i][j] = b[i - 2][j];
  } else {
    A = prm[0], G = prm[1], C = prm[2], T = prm[3];
    b[1][1] = A, b[2][1] = C, b[1][2] = G, b[2][2] = T;
    for (int i = 3; i <= N; i++) {
      if (i % 2 == 1) {
        if (fqlin[i][1][A] + fqlin[i][0][G] > fqlin[i][0][A] + fqlin[i][1][G])
          b[i][1] = A, b[i][2] = G;
        else
          b[i][1] = G, b[i][2] = A;
      } else {
        if (fqlin[i][1][C] + fqlin[i][0][T] > fqlin[i][0][C] + fqlin[i][1][T])
          b[i][1] = C, b[i][2] = T;
        else
          b[i][1] = T, b[i][2] = C;
      }
    }
    for (int i = 3; i <= M; i++)
      for (int j = 1; j <= N; j++) b[j][i] = b[j][i - 2];
  }
  for (int i = 1; i <= N; i++, printf("\n"))
    for (int j = 1; j <= M; j++) printf("%c", letters[b[i][j]]);
  return 0;
}
