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 int M = 998244353;
int n, i, m, A, C, o[4], j, sum, an = 1 << 30;
string c[300005], ans[300005], p[300005];
int compare() {
  int j, k, s = 0;
  for (j = 0; j < n; j++)
    for (k = 0; k < m; k++)
      if (ans[j][k] != c[j][k]) s++;
  return s;
}
void dfs(int i) {
  int j, k, flag = 0;
  if (i == 4) {
    for (j = 0; j < 4; j++)
      for (k = j + 1; k < 4; k++)
        if (o[j] == o[k]) flag = 1;
    if (flag == 0) {
      for (j = 0; j < n; j++) ans[j] = c[j];
      for (j = 0; j < n; j += 2) {
        A = C = 0;
        for (k = 0; k < m; k++) {
          if (k % 2 == 0) {
            if (c[j][k] != o[0]) A++;
            if (c[j][k] != o[1]) C++;
          } else {
            if (c[j][k] != o[0]) A--;
            if (c[j][k] != o[1]) C--;
          }
        }
        if (A < C) {
          for (k = 0; k < m; k += 2) ans[j][k] = o[0];
          for (k = 1; k < m; k += 2) ans[j][k] = o[1];
        } else {
          for (k = 0; k < m; k += 2) ans[j][k] = o[1];
          for (k = 1; k < m; k += 2) ans[j][k] = o[0];
        }
      }
      for (j = 1; j < n; j += 2) {
        A = C = 0;
        for (k = 0; k < m; k++) {
          if (k % 2 == 0) {
            if (c[j][k] != o[2]) A++;
            if (c[j][k] != o[3]) C++;
          } else {
            if (c[j][k] != o[2]) A--;
            if (c[j][k] != o[3]) C--;
          }
        }
        if (A < C) {
          for (k = 0; k < m; k += 2) ans[j][k] = o[2];
          for (k = 1; k < m; k += 2) ans[j][k] = o[3];
        } else {
          for (k = 0; k < m; k += 2) ans[j][k] = o[3];
          for (k = 1; k < m; k += 2) ans[j][k] = o[2];
        }
      }
      int s = compare();
      if (s < an) {
        an = s;
        for (j = 0; j < n; j++) p[j] = ans[j];
      }
      for (j = 0; j < n; j++) ans[j] = c[j];
      for (j = 0; j < m; j += 2) {
        A = C = 0;
        for (k = 0; k < n; k++) {
          if (k % 2 == 0) {
            if (c[k][j] != o[0]) A++;
            if (c[k][j] != o[1]) C++;
          } else {
            if (c[k][j] != o[0]) A--;
            if (c[k][j] != o[1]) C--;
          }
        }
        if (A < C) {
          for (k = 0; k < n; k += 2) ans[k][j] = o[0];
          for (k = 1; k < n; k += 2) ans[k][j] = o[1];
        } else {
          for (k = 0; k < n; k += 2) ans[k][j] = o[1];
          for (k = 1; k < n; k += 2) ans[k][j] = o[0];
        }
      }
      for (j = 1; j < m; j += 2) {
        A = C = 0;
        for (k = 0; k < n; k++) {
          if (k % 2 == 0) {
            if (c[k][j] != o[2]) A++;
            if (c[k][j] != o[3]) C++;
          } else {
            if (c[k][j] != o[2]) A--;
            if (c[k][j] != o[3]) C--;
          }
        }
        if (A < C) {
          for (k = 0; k < n; k += 2) ans[k][j] = o[2];
          for (k = 1; k < n; k += 2) ans[k][j] = o[3];
        } else {
          for (k = 0; k < n; k += 2) ans[k][j] = o[3];
          for (k = 1; k < n; k += 2) ans[k][j] = o[2];
        }
      }
      int ss = compare();
      if (ss < an) {
        an = ss;
        for (j = 0; j < n; j++) p[j] = ans[j];
      }
      sum++;
    }
    return;
  }
  o[i] = 'A';
  dfs(i + 1);
  o[i] = 'T';
  dfs(i + 1);
  o[i] = 'G';
  dfs(i + 1);
  o[i] = 'C';
  dfs(i + 1);
}
int main() {
  scanf("%d %d\n", &n, &m);
  for (i = 0; i < n; i++) cin >> c[i];
  dfs(0);
  for (i = 0; i < n; i++) {
    for (j = 0; j < m; j++) printf("%c", p[i][j]);
    printf("\n");
  }
}
