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 + 6;
string aux[N], s[N], sol[N], auxs[N];
int n, m;
bool f[4];
int tr[130], dp[N][4][4][3];
char inv[4];
int solve() {
  for (int i = 0; i < n; ++i) {
    for (int l = 0; l < 4; ++l) {
      for (int k = l + 1; k < 4; ++k) {
        f[l] = 1;
        f[k] = 1;
        int fs(-1), ss(-1);
        for (int j = 0; j < 4; ++j) {
          if (!f[j]) {
            if (fs == -1)
              fs = j;
            else
              ss = j;
          }
        }
        assert(fs >= 0);
        assert(ss >= 0);
        f[l] = 0;
        f[k] = 0;
        int a(0), b(0);
        for (int j = 0; j < m; ++j) {
          if (tr[s[i][j] - 'A'] != l) {
            if (j & 1)
              ++b;
            else
              ++a;
          }
          if (tr[s[i][j] - 'A'] != k) {
            if (j & 1)
              ++a;
            else
              ++b;
          }
        }
        if (i) {
          dp[i][l][k][1] = a + dp[i - 1][fs][ss][0];
          dp[i][l][k][2] = b + dp[i - 1][fs][ss][0];
        } else {
          dp[i][l][k][1] = a;
          dp[i][l][k][2] = b;
        }
        dp[i][l][k][0] = min(dp[i][l][k][1], dp[i][l][k][2]);
      }
    }
  }
  int cur(1e9), a(-1), b(-1);
  for (int l = 0; l < 4; ++l) {
    for (int k = l + 1; k < 4; ++k) {
      if (dp[n - 1][l][k][0] < cur) {
        cur = dp[n - 1][l][k][0];
        a = l;
        b = k;
      }
    }
  }
  for (int i = 0; i < n; ++i) sol[i].resize(m);
  if (dp[n - 1][a][b][0] == dp[n - 1][a][b][1]) {
    for (int j = 0; j < m; ++j) {
      if (j & 1)
        sol[n - 1][j] = inv[b];
      else
        sol[n - 1][j] = inv[a];
    }
  } else {
    for (int j = 0; j < m; ++j) {
      if (j & 1)
        sol[n - 1][j] = inv[a];
      else
        sol[n - 1][j] = inv[b];
    }
  }
  for (int i = n - 2; i >= 0; --i) {
    f[a] = 1;
    f[b] = 1;
    int fs(-1), ss(-1);
    for (int j = 0; j < 4; ++j) {
      if (!f[j]) {
        if (fs == -1)
          fs = j;
        else
          ss = j;
      }
    }
    assert(fs >= 0);
    assert(ss >= 0);
    f[a] = 0;
    f[b] = 0;
    if (dp[i][fs][ss][0] == dp[i][fs][ss][1]) {
      for (int j = 0; j < m; ++j) {
        if (j & 1)
          sol[i][j] = inv[ss];
        else
          sol[i][j] = inv[fs];
      }
    } else {
      for (int j = 0; j < m; ++j) {
        if (j & 1)
          sol[i][j] = inv[fs];
        else
          sol[i][j] = inv[ss];
      }
    }
    a = fs;
    b = ss;
  }
  return cur;
}
void spin() {
  for (int i = 0; i < m; ++i) aux[i].resize(n);
  for (int i = 0; i < n; ++i)
    for (int j = 0; j < m; ++j) aux[j][i] = s[i][j];
  swap(n, m);
  for (int i = 0; i < n; ++i) s[i] = aux[i];
}
int main() {
  tr['G' - 'A'] = 1;
  tr['C' - 'A'] = 2;
  tr['T' - 'A'] = 3;
  inv[0] = 'A';
  inv[1] = 'G';
  inv[2] = 'C';
  inv[3] = 'T';
  cin >> n >> m;
  for (int i = 0; i < n; ++i) cin >> s[i];
  int ans = solve();
  for (int i = 0; i < n; ++i) auxs[i] = sol[i];
  spin();
  int ans2 = solve();
  if (ans < ans2) {
    swap(n, m);
    for (int i = 0; i < n; ++i) s[i] = auxs[i];
  } else {
    for (int i = 0; i < n; ++i) s[i] = sol[i];
    spin();
  }
  for (int i = 0; i < n; ++i) cout << s[i] << '\n';
  return 0;
}
