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>
const int maxn = int(3e5) + 7;
char buf[maxn];
struct Matrix {
  char data[maxn];
  int n, m;
  bool reversed;
  int index(int x, int y) { return (x - 1) * m + y - 1; }
  char &at(int x, int y) { return data[index(x, y)]; }
  void reverse() {
    memcpy(buf, data, sizeof(char) * n * m);
    std::swap(n, m);
    for (int i = 1; i <= n; i++)
      for (int j = 1; j <= m; j++) at(i, j) = buf[(j - 1) * n + i - 1];
    reversed = !reversed;
  }
  void print() {
    if (reversed) reverse();
    for (int i = 1; i <= n; i++)
      for (int j = 1; j <= m; j++) printf("%c%s", at(i, j), j == m ? "\n" : "");
  }
  Matrix &operator=(const Matrix &tmp) {
    n = tmp.n, m = tmp.m, reversed = tmp.reversed;
    memcpy(data, tmp.data, sizeof(char) * n * m);
    return (*this);
  }
  int calc(const Matrix &mat, const char *table) {
    reversed = mat.reversed;
    n = mat.n, m = mat.m;
    int ret = 0;
    for (int i = 1; i <= n; i++) {
      int cur = (i & 1) << 1, min = 0x3f3f3f3f, best = -1;
      for (int k = 0; k < 2; k++) {
        int cnt = 0;
        for (int j = 1; j <= m; j++)
          if (mat.data[(i - 1) * m + j - 1] != table[cur + (j & 1) ^ k]) cnt++;
        if (cnt < min) min = cnt, best = k;
      }
      ret += min;
      for (int j = 1; j <= m; j++) at(i, j) = table[cur + (j & 1) ^ best];
    }
    return ret;
  }
  void read() {
    reversed = false;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
      for (int j = 1; j <= m; j++) scanf(" %c", &at(i, j));
  }
} ans, input;
int min = 0x3f3f3f3f;
void calc(const Matrix &mat) {
  char table[] = "AGCT";
  Matrix ret;
  do {
    int tmp = ret.calc(mat, table);
    if (tmp < min) min = tmp, ans = ret;
  } while (std::next_permutation(table, table + 4));
}
int main() {
  input.read();
  calc(input);
  input.reverse();
  calc(input);
  ans.print();
  return 0;
}
