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 long long MOD = 998244353;
const long long INF = 2e9 + 10;
const long long MAX = 1e14 + 10;
const long double EPS = 1e-9;
const int N = 3e5 + 10;
char ch[N];
string CH = "AGCT";
int NUM(char c) { return CH.find(c); }
vector<vector<int> > ans;
int d[2][N][5];
int tmp[N];
int solve1(int n, int m, int ansDif, vector<vector<int> >& a) {
  vector<int> perm = {0, 1, 2, 3};
  vector<vector<int> > temp(n, vector<int>(m, 0));
  do {
    int curDif = 0;
    for (int i = 0; i < n; i++) {
      int firstN = perm[0];
      int secondN = perm[1];
      if (i % 2) {
        firstN = perm[2];
        secondN = perm[3];
      }
      for (int j = 0; j < m; j += 2) {
        tmp[j] = firstN;
        tmp[j + 1] = secondN;
      }
      int cntNorm = 0;
      for (int j = 0; j < m; j++)
        if (a[i][j] != tmp[j]) cntNorm++;
      for (int j = 0; j <= m; j += 2) {
        tmp[j] = secondN;
        tmp[j + 1] = firstN;
      }
      int cntSw = 0;
      for (int j = 0; j < m; j++)
        if (a[i][j] != tmp[j]) cntSw++;
      if (cntNorm < cntSw) {
        for (int j = 0; j < m; j += 2) {
          tmp[j] = firstN;
          tmp[j + 1] = secondN;
        }
        curDif += cntNorm;
      } else {
        curDif += cntSw;
      }
      for (int j = 0; j < m; j++) temp[i][j] = tmp[j];
    }
    if (curDif < ansDif) {
      ansDif = curDif;
      ans = temp;
    }
  } while (next_permutation(perm.begin(), perm.end()));
  return ansDif;
}
int solve2(int n, int m, int ansDif, vector<vector<int> >& a) {
  vector<int> perm = {0, 1, 2, 3};
  vector<vector<int> > temp(n, vector<int>(m, 0));
  do {
    int curDif = 0;
    temp[0][0] = perm[0];
    temp[0][1] = perm[1];
    temp[1][0] = perm[2];
    temp[1][1] = perm[3];
    for (int j = 2; j < m; j++) {
      if (j % 2 == 0) {
        if (d[0][j][temp[0][0]] + d[1][j][temp[1][0]] <
            d[1][j][temp[0][0]] + d[0][j][temp[1][0]]) {
          temp[0][j] = temp[1][0];
          temp[1][j] = temp[0][0];
        } else {
          temp[0][j] = temp[0][0];
          temp[1][j] = temp[1][0];
        }
      } else {
        if (d[0][j][temp[0][1]] + d[1][j][temp[1][1]] <
            d[1][j][temp[0][1]] + d[0][j][temp[1][1]]) {
          temp[0][j] = temp[1][1];
          temp[1][j] = temp[0][1];
        } else {
          temp[0][j] = temp[0][1];
          temp[1][j] = temp[1][1];
        }
      }
    }
    for (int i = 2; i < n; i++)
      for (int j = 0; j < m; j++) temp[i][j] = temp[i % 2][j];
    for (int i = 0; i < n; i++)
      for (int j = 0; j < m; j++)
        if (a[i][j] != temp[i][j]) curDif++;
    if (curDif < ansDif) {
      ansDif = curDif;
      ans = temp;
    }
  } while (next_permutation(perm.begin(), perm.end()));
  return ansDif;
}
void solve() {
  int n, m;
  scanf("%d %d", &n, &m);
  vector<vector<int> > a(n, vector<int>(m));
  for (int i = 0; i < n; i++) {
    scanf("%s", &ch);
    for (int j = 0; j < m; j++) {
      a[i][j] = NUM(ch[j]);
    }
  }
  for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++) d[i % 2][j][a[i][j]]++;
  int dif = n * m + 1;
  int dif1 = solve1(n, m, dif, a);
  int tmp = solve2(n, m, dif1, a);
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) cout << CH[ans[i][j]];
    cout << endl;
  }
}
int main() { solve(); }
