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>
#pragma warning(disable : 4996)
#pragma comment(linker, "/STACK:336777216")
using namespace std;
int IT_MAX = 1 << 19;
const long long MOD = 1000000007;
const int INF = 0x3f3f3f3f;
const long long LL_INF = 0x3f3f3f3f3f3f3f3f;
const double PI = acos(-1);
const double ERR = 1e-10;
vector<string> in;
char tus[300050];
vector<string> ans;
vector<string> u;
int mnp[300050];
int main() {
  int N, M, i, j;
  scanf("%d %d", &N, &M);
  for (i = 0; i < N; i++) {
    scanf("%s", tus);
    in.emplace_back(tus);
  }
  ans = in;
  u = in;
  int mn = INF;
  char ch[5] = "ACGT";
  do {
    int tot = 0;
    for (int i = 0; i < N; i++) {
      char c[2] = {ch[0], ch[1]};
      if (i % 2 == 1) c[0] = ch[2], c[1] = ch[3];
      int v = INF;
      for (int j = 0; j < 2; j++) {
        int s = 0;
        for (int k = 0; k < M; k++) {
          if (c[j ^ (k & 1)] != in[i][k]) s++;
        }
        if (v > s) {
          v = s;
          mnp[i] = j;
        }
      }
      tot += v;
    }
    if (mn > tot) {
      for (int i = 0; i < N; i++) {
        char c[2] = {ch[0], ch[1]};
        if (i % 2 == 1) c[0] = ch[2], c[1] = ch[3];
        if (mnp[i]) swap(c[0], c[1]);
        for (int j = 0; j < M; j++) ans[i][j] = c[j & 1];
      }
      mn = tot;
    }
  } while (next_permutation(ch, ch + 4));
  do {
    int tot = 0;
    for (int i = 0; i < M; i++) {
      char c[2] = {ch[0], ch[1]};
      if (i % 2 == 1) c[0] = ch[2], c[1] = ch[3];
      int v = INF;
      for (int j = 0; j < 2; j++) {
        int s = 0;
        for (int k = 0; k < N; k++) {
          if (c[j ^ (k & 1)] != in[k][i]) s++;
        }
        if (v > s) {
          v = s;
          mnp[i] = j;
        }
      }
      tot += v;
    }
    if (mn > tot) {
      for (int i = 0; i < M; i++) {
        char c[2] = {ch[0], ch[1]};
        if (i % 2 == 1) c[0] = ch[2], c[1] = ch[3];
        if (mnp[i]) swap(c[0], c[1]);
        for (int j = 0; j < N; j++) ans[j][i] = c[j & 1];
      }
      mn = tot;
    }
  } while (next_permutation(ch, ch + 4));
  for (int i = 0; i < N; i++) printf("%s\n", ans[i].c_str());
  return 0;
}
