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 maxn = 3e5 + 10;
int n, m;
char ma[maxn];
int hexma[maxn];
int ans[maxn], tmp[maxn];
int rcal(int r, int a, int b) {
  int res = 0;
  for (int i = 0; i < m; i++) {
    tmp[(r * m + i)] = (i & 1) ? a : b;
    if (tmp[(r * m + i)] == hexma[(r * m + i)]) res++;
  }
  return res;
}
int ccal(int c, int a, int b) {
  int res = 0;
  for (int i = 0; i < n; i++) {
    tmp[(i * m + c)] = (i & 1) ? a : b;
    if (tmp[(i * m + c)] == hexma[(i * m + c)]) res++;
  }
  return res;
}
int rwork(int a, int b) {
  int c, d, t;
  int res = 0;
  a = 1 << a;
  b = 1 << b;
  t = (1 << 4) - 1 - a - b;
  c = t & -t;
  d = t - c;
  for (int i = 0; i < m; i++) {
    if (i & 1)
      tmp[i] = a;
    else
      tmp[i] = b;
    if (tmp[i] == hexma[i]) res++;
  }
  for (int i = 1; i < n; i++) {
    int p, q;
    if (i & 1)
      p = c, q = d;
    else
      p = a, q = b;
    int c1 = rcal(i, p, q), c2 = rcal(i, q, p);
    if (c1 < c2) swap(p, q), swap(c1, c2);
    ;
    res += c1;
    for (int j = 0; j < m; j++) tmp[(i * m + j)] = (j & 1) ? p : q;
  }
  return res;
}
int cwork(int a, int b) {
  int c, d, t;
  int res = 0;
  a = 1 << a;
  b = 1 << b;
  t = (1 << 4) - 1 - a - b;
  c = t & -t;
  d = t - c;
  for (int i = 0; i < n; i++) {
    if (i & 1)
      tmp[(i * m + 0)] = a;
    else
      tmp[(i * m + 0)] = b;
    if (tmp[(i * m + 0)] == hexma[(i * m + 0)]) res++;
  }
  for (int i = 1; i < m; i++) {
    int p, q;
    if (i & 1)
      p = c, q = d;
    else
      p = a, q = b;
    int c1 = ccal(i, p, q), c2 = ccal(i, q, p);
    if (c1 < c2) swap(p, q), swap(c1, c2);
    ;
    res += c1;
    for (int j = 0; j < n; j++) tmp[(j * m + i)] = (j & 1) ? p : q;
  }
  return res;
}
char rev(int x) {
  char res = 0;
  if (x == 1) res = 'A';
  if (x == 2) res = 'C';
  if (x == 4) res = 'G';
  if (x == 8) res = 'T';
  return res;
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 0; i < n; i++) {
    getchar();
    for (int j = 0; j < m; j++) {
      scanf("%c", &ma[(i * m + j)]);
      if (ma[(i * m + j)] == 'A') hexma[(i * m + j)] = 1;
      if (ma[(i * m + j)] == 'C') hexma[(i * m + j)] = 2;
      if (ma[(i * m + j)] == 'G') hexma[(i * m + j)] = 4;
      if (ma[(i * m + j)] == 'T') hexma[(i * m + j)] = 8;
    }
  }
  int now = 0;
  for (int i = 0; i < 4; i++) {
    for (int j = 0; j < 4; j++)
      if (i != j) {
        int temp = rwork(i, j);
        if (temp > now) {
          memcpy(ans, tmp, sizeof(int) * (n * m));
          now = temp;
        }
      }
  }
  for (int i = 0; i < 4; i++) {
    for (int j = 0; j < 4; j++)
      if (i != j) {
        int temp = cwork(i, j);
        if (temp > now) {
          memcpy(ans, tmp, sizeof(int) * (n * m));
          now = temp;
        }
      }
  }
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) printf("%c", rev(ans[(i * m + j)]));
    puts("");
  }
  return 0;
}
