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;
char t[12][3] = {{"AG"}, {"GA"}, {"AC"}, {"CA"}, {"AT"}, {"TA"},
                 {"GC"}, {"CG"}, {"GT"}, {"TG"}, {"TC"}, {"CT"}},
     **s;
int n, m, m1[300002], m2[300002], M1[300002], M2[300002];
int solveh() {
  int ret = 0;
  for (int i = 2; i <= n; i++) {
    int minn = 1050000000;
    for (int j = 0; j < 12; j++) {
      if (t[m1[i - 1]][0] == t[j][0] || t[m1[i - 1]][0] == t[j][1] ||
          t[m1[i - 1]][1] == t[j][0] || t[m1[i - 1]][1] == t[j][1])
        continue;
      int res = 0;
      for (int k = 1; k <= m; k++) {
        if (t[j][(k & 1) ^ 1] != s[i][k]) res++;
      }
      if (res < minn) {
        minn = res;
        m1[i] = j;
      }
    }
    ret += minn;
  }
  return ret;
}
int solvel() {
  int ret = 0;
  for (int i = 2; i <= m; i++) {
    int minn = 1050000000;
    for (int j = 0; j < 12; j++) {
      if (t[m2[i - 1]][0] == t[j][0] || t[m2[i - 1]][0] == t[j][1] ||
          t[m2[i - 1]][1] == t[j][0] || t[m2[i - 1]][1] == t[j][1])
        continue;
      int res = 0;
      for (int k = 1; k <= n; k++) {
        if (t[j][(k & 1) ^ 1] != s[k][i]) res++;
      }
      if (res < minn) {
        minn = res;
        m2[i] = j;
      }
    }
    ret += minn;
  }
  return ret;
}
int main() {
  scanf("%d%d", &n, &m);
  s = new char*[n + 1];
  for (int i = 1; i <= n; i++) {
    s[i] = new char[m + 2];
    scanf("%s", s[i] + 1);
  }
  int ans1 = 1050000000, ans2 = 1050000000;
  for (int j = 0; j < 12; j++) {
    m1[1] = j;
    int tmp = 0;
    for (int k = 1; k <= m; k++) {
      if (t[j][(k & 1) ^ 1] != s[1][k]) tmp++;
    }
    tmp += solveh();
    if (tmp < ans1) {
      ans1 = tmp;
      for (int i = 1; i <= n; i++) M1[i] = m1[i];
    }
  }
  for (int j = 0; j < 12; j++) {
    m2[1] = j;
    int tmp = 0;
    for (int k = 1; k <= n; k++) {
      if (t[j][(k & 1) ^ 1] != s[k][1]) tmp++;
    }
    tmp += solvel();
    if (tmp < ans2) {
      ans2 = tmp;
      for (int i = 1; i <= m; i++) M2[i] = m2[i];
    }
  }
  if (ans1 < ans2) {
    for (int i = 1; i <= n; i++) {
      for (int k = 1; k <= m; k++) {
        putchar(t[M1[i]][(k & 1) ^ 1]);
      }
      putchar('\n');
    }
  } else {
    for (int i = 1; i <= n; i++) {
      for (int k = 1; k <= m; k++) {
        putchar(t[M2[k]][(i & 1) ^ 1]);
      }
      putchar('\n');
    }
  }
  for (int i = 1; i <= n; i++) {
    delete s[i];
  }
  delete s;
  return 0;
}
