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;
template <typename T>
void chkmax(T &x, T y) {
  x = x > y ? x : y;
}
template <typename T>
void chkmin(T &x, T y) {
  x = x > y ? y : x;
}
const int INF = 2139062143;
template <typename T>
void read(T &x) {
  x = 0;
  bool f = 1;
  char ch;
  do {
    ch = getchar();
    if (ch == '-') f = 0;
  } while (ch > '9' || ch < '0');
  do {
    x = x * 10 + ch - '0';
    ch = getchar();
  } while (ch >= '0' && ch <= '9');
  x = f ? x : -x;
}
template <typename T>
void write(T x) {
  if (x < 0) x = ~x + 1, putchar('-');
  if (x > 9) write(x / 10);
  putchar(x % 10 + '0');
}
const int N = 3e5 + 7;
int n, m, ans;
string mp = "ACGT";
string a[N], cur[N], rev[N];
bool flag[N];
inline void calc(const string *a, int n, int m, bool rev) {
  int now = 0;
  for (int i = 0; i < n; i++) {
    int cnt0 = 0, cnt1 = 0;
    for (int j = 0; j < m; j++) {
      cnt0 += (mp[((i & 1) * 2) + (j & 1)] != a[i][j]);
      cnt1 += (mp[((i & 1) * 2) + !(j & 1)] != a[i][j]);
    }
    flag[i] = cnt0 < cnt1;
    now += min(cnt0, cnt1);
  }
  if (ans > now) {
    ans = now;
    if (rev) {
      for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
          cur[j][i] = flag[i] ? mp[((i & 1) * 2) + (j & 1)]
                              : mp[((i & 1) * 2) + !(j & 1)];
        }
      }
    } else {
      for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
          cur[i][j] = flag[i] ? mp[((i & 1) * 2) + (j & 1)]
                              : mp[((i & 1) * 2) + !(j & 1)];
        }
      }
    }
  }
}
int main() {
  ans = INF;
  read(n);
  read(m);
  for (int i = 0; i < n; i++) cin >> a[i], cur[i] = a[i];
  for (int i = 0; i < m; i++) rev[i].resize(n);
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      rev[j][i] = a[i][j];
    }
  }
  do {
    calc(a, n, m, 0);
    calc(rev, m, n, 1);
  } while (next_permutation(mp.begin(), mp.end()));
  for (int i = 0; i < n; i++) cout << cur[i] << "\n";
  return 0;
}
