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, a[300005], t, b, g, d[300005], ans;
int mk(int x, int y, int z, int w, int p) {
  if (p == 1) {
    int r = 0;
    for (int i = 1; i <= n; i++) {
      int p1 = 0, p2 = 0;
      for (int j = 1; j <= m; j++) {
        if (i & 1) {
          p1 += (a[((i - 1) * m + j)] == x && (j & 1)) +
                (a[((i - 1) * m + j)] == y && ((j & 1) ^ 1));
          p2 += (a[((i - 1) * m + j)] == y && (j & 1)) +
                (a[((i - 1) * m + j)] == x && ((j & 1) ^ 1));
        } else {
          p1 += (a[((i - 1) * m + j)] == z && (j & 1)) +
                (a[((i - 1) * m + j)] == w && ((j & 1) ^ 1));
          p2 += (a[((i - 1) * m + j)] == w && (j & 1)) +
                (a[((i - 1) * m + j)] == z && ((j & 1) ^ 1));
        }
      }
      if (p1 > p2) {
        for (int j = 1; j <= m; j++) {
          d[((i - 1) * m + j)] = (i & 1 ? (j & 1 ? x : y) : (j & 1 ? z : w));
        }
      } else {
        for (int j = 1; j <= m; j++) {
          d[((i - 1) * m + j)] = (i & 1 ? (j & 1 ? y : x) : (j & 1 ? w : z));
        }
      }
    }
    for (int i = 1; i <= n * m; i++) r += (d[i] != a[i]);
    return r;
  }
  if (p == 2) {
    int r = 0;
    for (int i = 1; i <= m; i++) {
      int p1 = 0, p2 = 0;
      for (int j = 1; j <= n; j++) {
        if (((j - 1) * m + i) > n * m)
          while (1)
            ;
        if (i & 1) {
          p1 += (a[((j - 1) * m + i)] == x && (j & 1)) +
                (a[((j - 1) * m + i)] == y && ((j & 1) ^ 1));
          p2 += (a[((j - 1) * m + i)] == y && (j & 1)) +
                (a[((j - 1) * m + i)] == x && ((j & 1) ^ 1));
        } else {
          p1 += (a[((j - 1) * m + i)] == z && (j & 1)) +
                (a[((j - 1) * m + i)] == w && ((j & 1) ^ 1));
          p2 += (a[((j - 1) * m + i)] == w && (j & 1)) +
                (a[((j - 1) * m + i)] == z && ((j & 1) ^ 1));
        }
      }
      if (p1 > p2) {
        for (int j = 1; j <= n; j++) {
          d[((j - 1) * m + i)] = (i & 1 ? (j & 1 ? x : y) : (j & 1 ? z : w));
        }
      } else {
        for (int j = 1; j <= n; j++) {
          d[((j - 1) * m + i)] = (i & 1 ? (j & 1 ? y : x) : (j & 1 ? w : z));
        }
      }
    }
    for (int i = 1; i <= n * m; i++) r += (d[i] != a[i]);
    return r;
  }
  return 10000000;
}
int main() {
  scanf("%d%d", &n, &m);
  map<char, int> m1;
  m1['A'] = 1, m1['T'] = 2, m1['G'] = 3, m1['C'] = 4;
  map<int, char> m2;
  m2[1] = 'A', m2[2] = 'T', m2[3] = 'G', m2[4] = 'C';
  for (int i = 1; i <= n * m; i++) {
    char c;
    scanf(" %c", &c);
    a[i] = m1[c];
  }
  int x1[] = {0, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2,
              3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4},
      x2[] = {0, 2, 2, 3, 3, 4, 4, 1, 1, 3, 3, 4, 4,
              1, 1, 2, 2, 4, 4, 1, 1, 2, 2, 3, 3},
      x3[] = {0, 3, 4, 2, 4, 2, 3, 3, 4, 1, 4, 1, 3,
              2, 4, 1, 4, 1, 2, 2, 3, 1, 3, 1, 2},
      x4[] = {0, 4, 3, 4, 2, 3, 2, 4, 3, 4, 1, 3, 1,
              4, 2, 4, 1, 2, 1, 3, 2, 3, 1, 2, 1},
      y = mk(1, 2, 3, 4, 1), z1 = 1, z2 = 2, z3 = 3, z4 = 4, z5 = 1;
  for (int i = 1; i <= 24; i++) {
    if (mk(x1[i], x2[i], x3[i], x4[i], 1) < y) {
      z1 = x1[i], z2 = x2[i], z3 = x3[i], z4 = x4[i], z5 = 1;
      y = mk(z1, z2, z3, z4, z5);
    }
    if (mk(x1[i], x2[i], x3[i], x4[i], 2) < y) {
      z1 = x1[i], z2 = x2[i], z3 = x3[i], z4 = x4[i], z5 = 2;
      y = mk(z1, z2, z3, z4, z5);
    }
  }
  mk(z1, z2, z3, z4, z5);
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      printf("%c", m2[d[((i - 1) * m + j)]]);
    }
    puts("");
  }
  return 0;
}
