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 N = 3e5 + 9;
int n, m;
int ans = 1e9 + 7;
vector<int> g[N], invg[N], dans[N], tmp[N], tmp1[N], tmp2[N];
bool flag = 0;
int solve(int n, int m, vector<int> g[N], int tg) {
  for (int i = 1; i <= n; i++)
    tmp[i].resize(m + 1), tmp1[i].resize(m + 1), tmp2[i].resize(m + 1);
  for (int i = 0; i <= 3; i++)
    for (int j = i + 1; j <= 3; j++) {
      int x1 = i, x2 = j, y1 = -1, y2 = -1, x, y;
      for (int k = 0; k <= 3; k++)
        if (k != i && k != j) {
          if (y1 == -1)
            y1 = k;
          else
            y2 = k;
        }
      int sum = 0;
      for (int ii = 1; ii <= n; ii++) {
        if (ii & 1)
          x = x1, y = x2;
        else
          x = y1, y = y2;
        int cnt1 = 0, cnt2 = 0;
        for (int jj = 1; jj <= m; jj++) {
          if (jj & 1) {
            tmp1[ii][jj] = x;
            if (g[ii][jj] != x) cnt1++;
          } else {
            tmp1[ii][jj] = y;
            if (g[ii][jj] != y) cnt1++;
          }
          if (jj & 1) {
            tmp2[ii][jj] = y;
            if (g[ii][jj] != y) cnt2++;
          } else {
            tmp2[ii][jj] = x;
            if (g[ii][jj] != x) cnt2++;
          }
        }
        sum += min(cnt1, cnt2);
        if (cnt1 <= cnt2)
          tmp[ii] = tmp1[ii];
        else
          tmp[ii] = tmp2[ii];
      }
      if (ans > sum) {
        flag = (tg == -1);
        ans = sum;
        for (int ii = 1; ii <= n; ii++) dans[ii] = tmp[ii];
      }
    }
  return ans;
}
char cc[9] = {'A', 'G', 'C', 'T'};
int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> n >> m;
  char c;
  for (int i = 1; i <= n; i++) g[i].resize(m + 1);
  for (int i = 1; i <= m; i++) invg[i].resize(n + 1);
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++) {
      cin >> c;
      if (c == 'A')
        g[i][j] = invg[j][i] = 0;
      else if (c == 'G')
        g[i][j] = invg[j][i] = 1;
      else if (c == 'C')
        g[i][j] = invg[j][i] = 2;
      else
        g[i][j] = invg[j][i] = 3;
    }
  int ans = min(solve(n, m, g, 1), solve(m, n, invg, -1));
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++)
      if (!flag)
        cout << cc[dans[i][j]];
      else
        cout << cc[dans[j][i]];
    cout << endl;
  }
  return 0;
}
