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 n, m, best;
char *s[300005], t[300005], base[5], temp[2][2], ans[300005], draw[300005];
int main() {
  scanf("%d %d", &n, &m);
  best = n * m;
  for (int i = (0); i < (n); i++) {
    scanf("%s", t + i * m);
    s[i] = t + i * m;
  }
  strcpy(base, "ACGT");
  for (int i = (0); i < (4); i++)
    for (int j = (i + 1); j < (4); j++) {
      temp[0][0] = base[i];
      temp[0][1] = base[j];
      int ptr = 0;
      for (int k = (0); k < (4); k++) {
        if (k != i && k != j) {
          temp[1][ptr++] = base[k];
        }
      }
      int tot = 0;
      for (int ii = (0); ii < (n); ii++) {
        int sum = 0, rev = 0;
        for (int jj = (0); jj < (m); jj++)
          if (s[ii][jj] != temp[ii % 2][jj % 2]) sum++;
        for (int jj = (0); jj < (m); jj++)
          if (s[ii][jj] != temp[ii % 2][(jj + 1) % 2]) rev++;
        if (sum <= rev) {
          for (int jj = (0); jj < (m); jj++)
            draw[ii * m + jj] = temp[ii % 2][jj % 2];
        } else {
          for (int jj = (0); jj < (m); jj++)
            draw[ii * m + jj] = temp[ii % 2][(jj + 1) % 2];
        }
        tot += min(sum, rev);
      }
      if (tot < best) {
        strcpy(ans, draw);
        best = tot;
      }
      tot = 0;
      for (int jj = (0); jj < (m); jj++) {
        int sum = 0, rev = 0;
        for (int ii = (0); ii < (n); ii++)
          if (s[ii][jj] != temp[jj % 2][ii % 2]) sum++;
        for (int ii = (0); ii < (n); ii++)
          if (s[ii][jj] != temp[jj % 2][(ii + 1) % 2]) rev++;
        if (sum <= rev) {
          for (int ii = (0); ii < (n); ii++)
            draw[ii * m + jj] = temp[jj % 2][ii % 2];
        } else {
          for (int ii = (0); ii < (n); ii++)
            draw[ii * m + jj] = temp[jj % 2][(ii + 1) % 2];
        }
        tot += min(sum, rev);
      }
      if (tot < best) {
        strcpy(ans, draw);
        best = tot;
      }
    }
  for (int i = (0); i < (n); i++) {
    for (int j = (0); j < (m); j++) printf("%c", ans[i * m + j]);
    puts("");
  }
}
