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 NM = 300005;
char p[12][2] = {{'0', '1'}, {'0', '2'}, {'0', '3'}, {'1', '2'},
                 {'1', '3'}, {'2', '3'}, {'1', '0'}, {'2', '0'},
                 {'3', '0'}, {'2', '1'}, {'3', '1'}, {'3', '2'}};
int ok[12][12];
void work_init() {
  for (int k1 = 0; k1 < 12; k1++)
    for (int k2 = 0; k2 < 12; k2++) {
      ok[k1][k2] = 1;
      for (int i = 0; i < 2; i++)
        for (int j = 0; j < 2; j++)
          if (p[k1][i] == p[k2][j]) ok[k1][k2] = 0;
    }
}
int work(int n, int m, vector<char> *a, vector<char> *c) {
  static int f[NM][12], pre[NM][12];
  for (int k2 = 0; k2 < 12; k2++) {
    int cnt = 0;
    for (int j = 0; j < m; j++) cnt += a[0][j] != p[k2][j & 1];
    f[0][k2] = cnt;
  }
  for (int i = 1; i < n; i++) {
    memset(f[i], 0x3f, sizeof(f[i]));
    for (int k1 = 0; k1 < 12; k1++)
      for (int k2 = 0; k2 < 12; k2++)
        if (ok[k1][k2]) {
          int cnt = 0;
          for (int j = 0; j < m; j++) cnt += a[i][j] != p[k2][j & 1];
          if (f[i][k2] > f[i - 1][k1] + cnt)
            f[i][k2] = f[i - 1][k1] + cnt, pre[i][k2] = k1;
        }
  }
  int mk = 0;
  for (int k2 = 0; k2 < 12; k2++)
    if (f[n - 1][k2] < f[n - 1][mk]) mk = k2;
  for (int i = n - 1, t = mk; i >= 0; t = pre[i][t], i--) {
    for (int j = 0; j < m; j++) c[i].push_back(p[t][j & 1]);
  }
  return f[n - 1][mk];
}
char tra0[130], tra1[130];
void trans_init() {
  tra0['A'] = '0', tra1['0'] = 'A';
  tra0['C'] = '1', tra1['1'] = 'C';
  tra0['G'] = '2', tra1['2'] = 'G';
  tra0['T'] = '3', tra1['3'] = 'T';
}
char trans(char x, int f) {
  if (!f)
    return tra0[x];
  else
    return tra1[x];
}
vector<char> a[NM], b[NM], f[NM], g[NM];
int main() {
  trans_init();
  work_init();
  int i, j, n, m;
  cin >> n >> m;
  for (i = 0; i < n; i++) {
    static char s[NM];
    scanf("%s", s);
    for (j = 0; j < m; j++) a[i].push_back(trans(s[j], 0));
  }
  int ans1 = work(n, m, a, f);
  for (i = 0; i < n; i++)
    for (j = 0; j < m; j++) b[j].push_back(a[i][j]);
  int ans2 = work(m, n, b, g);
  if (ans1 > ans2) {
    for (i = 0; i < n; i++) f[i].clear();
    for (j = 0; j < m; j++)
      for (i = 0; i < n; i++) f[i].push_back(g[j][i]);
  }
  for (i = 0; i < n; i++) {
    for (j = 0; j < m; j++) printf("%c", trans(f[i][j], 1));
    puts("");
  }
  return 0;
}
