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;
int n, m, ans, flag;
string mat[300005];
char pr[10] = "ACGT", sol[10];
int solve_row(int d = 0) {
  int res = 0;
  for (int i = 0; i <= n - 1; ++i) {
    char a[2];
    if (i & 1) {
      a[0] = pr[0];
      a[1] = pr[1];
    } else {
      a[0] = pr[2];
      a[1] = pr[3];
    }
    int sa = 0, sb = 0;
    for (int j = 0; j <= m - 1; ++j) {
      sa += mat[i][j] != a[j & 1];
      sb += mat[i][j] != a[!(j & 1)];
    }
    if (sa < sb) {
      res += sa;
      if (d)
        for (int j = 0; j <= m - 1; ++j) mat[i][j] = a[j & 1];
    } else {
      res += sb;
      if (d)
        for (int j = 0; j <= m - 1; ++j) mat[i][j] = a[!(j & 1)];
    }
  }
  return res;
}
int solve_col(int d = 0) {
  int res = 0;
  for (int i = 0; i <= m - 1; ++i) {
    char a[2];
    if (i & 1) {
      a[0] = pr[0];
      a[1] = pr[1];
    } else {
      a[0] = pr[2];
      a[1] = pr[3];
    }
    int sa = 0, sb = 0;
    for (int j = 0; j <= n - 1; ++j) {
      sa += mat[j][i] != a[j & 1];
      sb += mat[j][i] != a[!(j & 1)];
    }
    if (sa < sb) {
      res += sa;
      if (d)
        for (int j = 0; j <= n - 1; ++j) mat[j][i] = a[j & 1];
    } else {
      res += sb;
      if (d)
        for (int j = 0; j <= n - 1; ++j) mat[j][i] = a[!(j & 1)];
    }
  }
  return res;
}
int main() {
  ios::sync_with_stdio(false);
  cin >> n >> m;
  ans = n * m;
  for (int i = 0; i <= n - 1; ++i) cin >> mat[i];
  do {
    int t;
    if ((t = solve_row()) < ans) {
      ans = t;
      strcpy(sol, pr);
      flag = 0;
    }
    if ((t = solve_col()) < ans) {
      ans = t;
      strcpy(sol, pr);
      flag = 1;
    }
  } while (next_permutation(pr, pr + 4));
  strcpy(pr, sol);
  if (!flag)
    solve_row(1);
  else
    solve_col(1);
  for (int i = 0; i <= n - 1; ++i) cout << mat[i] << endl;
  return 0;
}
