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 + 5;
string s[N], t[N], a[N], b[N], r[N];
int n, m;
inline void flip(string x[N], int u, int v) {
  for (int i = 0; i < v; i++) r[i].clear();
  for (int i = 0; i < u; i++)
    for (int j = 0; j < v; j++) r[j] += x[i][j];
  for (int i = 0; i < v; i++) x[i] = r[i];
}
inline int check() {
  int k = 0;
  string c[4] = {"A", "C", "G", "T"};
  do {
    int ans = 0;
    string x[2] = {}, y[2] = {};
    for (int i = 0; i < m; i++)
      for (int j = 0; j < 2; j++) {
        x[j] += c[i & 1 ^ j];
        y[j] += c[i & 1 ^ j | 2];
      }
    for (int i = 0; i < n; i++) {
      int cnt[2] = {};
      for (int j = 0; j < m; j++)
        for (int k = 0; k < 2; k++)
          cnt[k] += ((i & 1 ? y : x)[k][j] == a[i][j]);
      r[i] = (i & 1 ? y : x)[cnt[1] > cnt[0]];
      ans += cnt[cnt[1] > cnt[0]];
    }
    if (ans > k) {
      k = ans;
      for (int i = 0; i < n; i++) b[i] = r[i];
    }
  } while (next_permutation(c, c + 4));
  return k;
}
inline void readInput() {
  cin >> n >> m;
  for (int i = 0; i < n; i++) cin >> s[i];
}
inline void solve() {
  int mx = 0;
  for (int i = 0; i < n; i++) a[i] = s[i];
  for (int i = 0; i < 4; i++) {
    int k = check();
    if (mx < k) {
      for (int j = 0; j < 4 - i; j++) {
        flip(b, n, m);
        swap(n, m);
      }
      for (int j = 0; j < n; j++) t[j] = b[j];
      if (4 - i & 1) swap(n, m);
      mx = k;
    }
    flip(a, n, m);
    swap(n, m);
  }
}
inline void writeOutput() {
  for (int i = 0; i < n; i++) cout << t[i] << endl;
}
int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  readInput(), solve(), writeOutput();
  return 0;
}
