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 MAXN = 300010;
const int INF = 1000000010;
char letters[] = {'A', 'T', 'G', 'C'};
int n, m;
int costLine[MAXN][4][4];
string v[MAXN];
string ans[MAXN];
string aux[MAXN];
void rotate() {
  for (int i = 0; i < n; i++) {
    aux[i] = v[i];
    v[i].clear();
  }
  for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++) v[j].push_back(aux[i][j]);
  swap(n, m);
}
int decode(char a) {
  for (int i = 0; i < 4; i++)
    if (letters[i] == a) return i;
}
char encode(int a) { return letters[a]; }
int calculate() {
  int c[4];
  for (int i = 0; i < n; i++) {
    for (c[0] = 0; c[0] < 4; c[0]++) {
      for (c[1] = 0; c[1] < 4; c[1]++) {
        int& curAns = costLine[i][c[0]][c[1]];
        curAns = 0;
        for (int j = 0; j < m; j++)
          if (decode(v[i][j]) != c[j % 2]) curAns++;
      }
    }
  }
  int optC[4];
  int optValue = INF;
  for (c[0] = 0; c[0] < 4; c[0]++) {
    for (c[1] = c[0] + 1; c[1] < 4; c[1]++) {
      if (c[0] > 0)
        c[2] = 0;
      else if (c[1] == 1)
        c[2] = 2;
      else
        c[2] = 1;
      c[3] = 6 - c[0] - c[1] - c[2];
      int sum = 0;
      for (int i = 0; i < n; i++) {
        int ind = 2 * (i % 2);
        int val = costLine[i][c[ind]][c[ind + 1]];
        val = min(val, costLine[i][c[ind + 1]][c[ind]]);
        sum += val;
      }
      if (sum < optValue) {
        for (int i = 0; i < 4; i++) optC[i] = c[i];
        optValue = sum;
      }
    }
  }
  for (int i = 0; i < n; i++) {
    int ind = 2 * (i % 2);
    if (costLine[i][optC[ind]][optC[ind + 1]] >
        costLine[i][optC[ind + 1]][optC[ind]])
      swap(optC[ind], optC[ind + 1]);
    ans[i].clear();
    for (int j = 0; j < m; j++) ans[i].push_back(encode(optC[ind + j % 2]));
  }
  return optValue;
}
int main() {
  scanf("%d %d", &n, &m);
  for (int i = 0; i < n; i++) cin >> v[i];
  int ansLine = calculate();
  rotate();
  int ansColumn = calculate();
  if (ansLine < ansColumn) rotate();
  calculate();
  if (ansLine < ansColumn) {
    for (int i = 0; i < n; i++, printf("\n"))
      for (int j = 0; j < m; j++) printf("%c", ans[i][j]);
  } else {
    for (int i = 0; i < m; i++, printf("\n"))
      for (int j = 0; j < n; j++) printf("%c", ans[j][i]);
  }
}
