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 INF = 1000000000, N = 300010;
const string pat[6] = {"AC", "AG", "AT", "CG", "CT", "GT"};
string st[N];
int rpt[N], cpt[N], ansrpt[N], anscpt[N], currpt[N], curcpt[N];
int n, m, ansr[2], ansc[2];
int rcalc(int pt, int odd, int row) {
  int cnt = 0;
  for (int j = 0; j < m; j++)
    if (st[row][j] != pat[pt][(j & 1) ^ odd]) cnt++;
  return cnt;
}
int ccalc(int pt, int odd, int col) {
  int cnt = 0;
  for (int i = 0; i < n; i++)
    if (st[i][col] != pat[pt][(i & 1) ^ odd]) cnt++;
  return cnt;
}
int main() {
  ios::sync_with_stdio(false);
  cin >> n >> m;
  for (int i = 0; i < n; i++) cin >> st[i];
  int rmin = INF, cmin = INF;
  for (rpt[0] = 0; rpt[0] < 6; rpt[0]++) {
    rpt[1] = 5 - rpt[0];
    int cnt = 0;
    for (int i = 0; i < n; i++) {
      int cnt0 = rcalc(rpt[i & 1], 0, i), cnt1 = rcalc(rpt[i & 1], 1, i);
      if (cnt0 <= cnt1) {
        currpt[i] = 0;
        cnt += cnt0;
      } else {
        currpt[i] = 1;
        cnt += cnt1;
      }
    }
    if (cnt < rmin) {
      rmin = cnt;
      ansr[0] = rpt[0];
      ansr[1] = rpt[1];
      for (int i = 0; i < n; i++) ansrpt[i] = currpt[i];
    }
  }
  for (cpt[0] = 0; cpt[0] < 6; cpt[0]++) {
    cpt[1] = 5 - cpt[0];
    int cnt = 0;
    for (int j = 0; j < m; j++) {
      int cnt0 = ccalc(cpt[j & 1], 0, j), cnt1 = ccalc(cpt[j & 1], 1, j);
      if (cnt0 <= cnt1) {
        curcpt[j] = 0;
        cnt += cnt0;
      } else {
        curcpt[j] = 1;
        cnt += cnt1;
      }
    }
    if (cnt < cmin) {
      cmin = cnt;
      ansc[0] = cpt[0];
      ansc[1] = cpt[1];
      for (int j = 0; j < m; j++) anscpt[j] = curcpt[j];
    }
  }
  if (rmin <= cmin) {
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) cout << pat[ansr[i & 1]][ansrpt[i] ^ (j & 1)];
      cout << "\n";
    }
  } else {
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) cout << pat[ansc[j & 1]][anscpt[j] ^ (i & 1)];
      cout << "\n";
    }
  }
}
