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;
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
int const N = 3e5 + 20, inf = 1e9 + 20;
int n, m;
string s[N];
char ch[4] = {'A', 'G', 'C', 'T'};
int per[4];
int res = inf;
int best[4];
bool f;
int main() {
  ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  cin >> n >> m;
  for (int i = 0; i < n; i++) cin >> s[i];
  iota(per, per + 4, 0);
  do {
    char a[4];
    for (int i = 0; i < 4; i++) a[i] = ch[per[i]];
    int cnt = 0;
    for (int i = 0; i < n; i++) {
      int val = inf;
      for (int f = 0; f < 2; f++) {
        char b[2];
        b[0] = a[(2 * (i & 1)) ^ f], b[1] = a[((2 * (i & 1)) + 1) ^ f];
        int cc = 0;
        for (int j = 0; j < m; j++) cc += (s[i][j] != b[j & 1]);
        val = min(val, cc);
      }
      cnt += val;
    }
    if (cnt < res) {
      res = cnt;
      for (int i = 0; i < 4; i++) best[i] = per[i];
      f = 0;
    }
    cnt = 0;
    for (int j = 0; j < m; j++) {
      int val = inf;
      for (int f = 0; f < 2; f++) {
        char b[2];
        b[0] = a[(2 * (j & 1)) ^ f], b[1] = a[((2 * (j & 1)) + 1) ^ f];
        int cc = 0;
        for (int i = 0; i < n; i++) cc += (s[i][j] != b[i & 1]);
        val = min(val, cc);
      }
      cnt += val;
    }
    if (cnt < res) {
      res = cnt;
      for (int i = 0; i < 4; i++) best[i] = per[i];
      f = 1;
    }
  } while (next_permutation(per, per + 4));
  if (f) {
    for (int j = 0; j < m; j++) {
      int val = inf, bb = -1;
      for (int f = 0; f < 2; f++) {
        char b[2];
        b[0] = ch[best[(2 * (j & 1)) ^ f]],
        b[1] = ch[best[((2 * (j & 1)) + 1) ^ f]];
        int cc = 0;
        for (int i = 0; i < n; i++) cc += (s[i][j] != b[i & 1]);
        if (cc < val) bb = f, val = cc;
      }
      char b[2];
      b[0] = ch[best[(2 * (j & 1)) ^ bb]],
      b[1] = ch[best[((2 * (j & 1)) + 1) ^ bb]];
      for (int i = 0; i < n; i++) s[i][j] = b[i & 1];
    }
  } else {
    for (int i = 0; i < n; i++) {
      int val = inf, bb = -1;
      for (int f = 0; f < 2; f++) {
        char b[2];
        b[0] = ch[best[(2 * (i & 1)) ^ f]],
        b[1] = ch[best[((2 * (i & 1)) + 1) ^ f]];
        int cc = 0;
        for (int j = 0; j < m; j++) cc += (s[i][j] != b[j & 1]);
        if (cc < val) bb = f, val = cc;
      }
      char b[2];
      b[0] = ch[best[(2 * (i & 1)) ^ bb]],
      b[1] = ch[best[((2 * (i & 1)) + 1) ^ bb]];
      for (int j = 0; j < m; j++) s[i][j] = b[j & 1];
    }
  }
  for (int i = 0; i < n; i++) {
    cout << s[i] << '\n';
  }
}
