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 maxn = 100000;
vector<pair<char, char> > fv, v;
bool is_r;
int num[26][2];
void f(char a, char b, char &c, char &d) {
  c = 0;
  char x[] = {'A', 'T', 'C', 'G'};
  for (int i = 0; i < 4; i++)
    if (x[i] != a && x[i] != b) {
      if (c)
        d = x[i];
      else
        c = x[i];
    }
}
int main() {
  int n, m;
  char *s;
  is_r = 1;
  scanf("%d%d", &n, &m);
  s = (char *)malloc(sizeof(char) * m * n);
  getchar();
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) scanf("%c", s + i * m + j);
    getchar();
  }
  char x[] = {'A', 'T', 'C', 'G'};
  int res = 0, tmp;
  for (int i = 0; i < 3; i++)
    for (int j = i + 1; j < 4; j++) {
      tmp = 0;
      for (int r = 0; r < n; r++) {
        for (int c = 0; c < m; c++) {
          char now = *(s + r * m + c);
          num[now - 'A'][c & 1]++;
        }
        if (r & 1) {
          char c1, c2;
          f(x[i], x[j], c1, c2);
          if (num[c1 - 'A'][0] + num[c2 - 'A'][1] >
              num[c1 - 'A'][1] + num[c2 - 'A'][0]) {
            tmp += num[c1 - 'A'][0] + num[c2 - 'A'][1];
            v.push_back(pair<char, char>(c1, c2));
          } else {
            tmp += num[c1 - 'A'][1] + num[c2 - 'A'][0];
            v.push_back(pair<char, char>(c2, c1));
          }
        } else {
          if (num[x[i] - 'A'][0] + num[x[j] - 'A'][1] >
              num[x[i] - 'A'][1] + num[x[j] - 'A'][0]) {
            tmp += num[x[i] - 'A'][0] + num[x[j] - 'A'][1];
            v.push_back(pair<char, char>(x[i], x[j]));
          } else {
            tmp += num[x[i] - 'A'][1] + num[x[j] - 'A'][0];
            v.push_back(pair<char, char>(x[j], x[i]));
          }
        }
        memset(num, 0, sizeof(num));
      }
      if (res < tmp) {
        is_r = 1;
        res = tmp;
        fv = v;
      }
      v.clear();
      tmp = 0;
      for (int c = 0; c < m; c++) {
        for (int r = 0; r < n; r++) {
          char now = *(s + r * m + c);
          num[now - 'A'][r & 1]++;
        }
        if (c & 1) {
          char c1, c2;
          f(x[i], x[j], c1, c2);
          if (num[c1 - 'A'][0] + num[c2 - 'A'][1] >
              num[c1 - 'A'][1] + num[c2 - 'A'][0]) {
            tmp += num[c1 - 'A'][0] + num[c2 - 'A'][1];
            v.push_back(pair<char, char>(c1, c2));
          } else {
            tmp += num[c1 - 'A'][1] + num[c2 - 'A'][0];
            v.push_back(pair<char, char>(c2, c1));
          }
        } else {
          if (num[x[i] - 'A'][0] + num[x[j] - 'A'][1] >
              num[x[i] - 'A'][1] + num[x[j] - 'A'][0]) {
            tmp += num[x[i] - 'A'][0] + num[x[j] - 'A'][1];
            v.push_back(pair<char, char>(x[i], x[j]));
          } else {
            tmp += num[x[i] - 'A'][1] + num[x[j] - 'A'][0];
            v.push_back(pair<char, char>(x[j], x[i]));
          }
        }
        memset(num, 0, sizeof(num));
      }
      if (res < tmp) {
        is_r = 0;
        res = tmp;
        fv = v;
      }
      v.clear();
      res = max(res, tmp);
    }
  if (is_r) {
    for (int r = 0; r < n; r++) {
      for (int j = 0; j < m / 2; j++) {
        putchar(fv[r].first);
        putchar(fv[r].second);
      }
      if (m & 1) putchar(fv[r].first);
      putchar('\n');
    }
  } else {
    for (int c = 0; c < m; c++) {
      for (int r = 0; r < n / 2; r++) {
        int now = 2 * r * m + c;
        *(s + now) = fv[c].first;
        *(s + now + m) = fv[c].second;
      }
      if (n & 1) *(s + (n - 1) * m + c) = fv[c].first;
    }
    for (int r = 0; r < n; r++) {
      for (int c = 0; c < m; c++) putchar(*(s + r * m + c));
      putchar('\n');
    }
  }
  return 0;
}
