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 DN = 3e5 + 5;
int n, m, sol, f, cnt, mi = 1e9, sum;
char ch[6], a[5][5], car;
string s[DN], r[DN];
void solve1() {
  cnt++;
  sum = 0;
  int f, mi;
  for (int i = 1; i <= n; i++) {
    f = 0;
    for (int j = 1; j <= m; j++) {
      car = a[i % 2][j % 2];
      if (s[i][j] != car) f++;
      r[i][j] = car;
    }
    mi = f;
    f = 0;
    for (int j = 1; j <= m; j++) {
      car = a[i % 2][1 - j % 2];
      if (s[i][j] != car) f++;
    }
    if (f < mi) {
      mi = f;
      for (int j = 1; j <= m; j++) {
        car = a[i % 2][1 - j % 2];
        r[i][j] = car;
      }
    }
    sum += mi;
  }
}
void solve2() {
  cnt++;
  sum = 0;
  int f, mi;
  for (int j = 1; j <= m; j++) {
    f = 0;
    for (int i = 1; i <= n; i++) {
      car = a[i % 2][j % 2];
      if (s[i][j] != car) f++;
      r[i][j] = car;
    }
    mi = f;
    f = 0;
    for (int i = 1; i <= n; i++) {
      car = a[1 - i % 2][j % 2];
      if (s[i][j] != car) f++;
    }
    if (f < mi) {
      mi = f;
      for (int i = 1; i <= n; i++) {
        car = a[1 - i % 2][j % 2];
        r[i][j] = car;
      }
    }
    sum += mi;
  }
}
void solve() {
  cnt = 0;
  ch[1] = 'A';
  ch[2] = 'G';
  ch[3] = 'C';
  ch[4] = 'T';
  do {
    a[0][0] = ch[1];
    a[0][1] = ch[2];
    a[1][0] = ch[3];
    a[1][1] = ch[4];
    solve1();
    if (sum < mi) {
      mi = sum;
      f = cnt;
    }
    if (sum == sol) return;
    solve2();
    if (sum < mi) {
      mi = sum;
      f = cnt;
    }
    if (sum == sol) return;
  } while (next_permutation(ch + 1, ch + 5));
  sol = mi;
}
int main() {
  cin.sync_with_stdio(false);
  cout.sync_with_stdio(false);
  cin >> n >> m;
  for (int i = 0; i <= n; i++) getline(cin, s[i]);
  for (int i = 1; i <= n; i++) {
    s[i] = " " + s[i];
    r[i] = s[i];
  }
  solve();
  solve();
  for (int i = 1; i <= n; i++) r[i].erase(r[i].begin());
  for (int i = 1; i <= n; i++) cout << r[i] << '\n';
}
