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;
int n, m;
char s[N];
vector<int> a[N], b[N], c[N], d[N];
int calc(int c1, int c2, int n, int m, vector<int> *a) {
  int c3, c4, res = 0;
  for (int i = (1); i <= (4); ++i)
    if (i != c1 && i != c2) {
      c3 = i;
      break;
    }
  for (int i = (1); i <= (4); ++i)
    if (i != c1 && i != c2 && i != c3) {
      c4 = i;
      break;
    }
  for (int i = (1); i <= (n); ++i) {
    int t1, t2, mn = m + 1, tmp = 0;
    if (i & 1)
      t1 = c1, t2 = c2;
    else
      t1 = c3, t2 = c4;
    for (int j = (1); j <= (m); ++j) {
      if ((j & 1) && a[i][j] != t1) ++tmp;
      if (((j & 1) ^ 1) && a[i][j] != t2) ++tmp;
    }
    mn = min(mn, tmp), swap(t1, t2), tmp = 0;
    for (int j = (1); j <= (m); ++j) {
      if ((j & 1) && a[i][j] != t1) ++tmp;
      if (((j & 1) ^ 1) && a[i][j] != t2) ++tmp;
    }
    mn = min(mn, tmp), res += mn;
  }
  return res;
}
void otp(int c1, int c2, int n, int m, vector<int> *a, vector<int> *b) {
  int c3, c4;
  for (int i = (1); i <= (4); ++i)
    if (i != c1 && i != c2) {
      c3 = i;
      break;
    }
  for (int i = (1); i <= (4); ++i)
    if (i != c1 && i != c2 && i != c3) {
      c4 = i;
      break;
    }
  for (int i = (1); i <= (n); ++i) {
    int t1, t2, mn = m + 1, tmp = 0;
    if (i & 1)
      t1 = c1, t2 = c2;
    else
      t1 = c3, t2 = c4;
    for (int j = (1); j <= (m); ++j) {
      if ((j & 1) && a[i][j] != t1) ++tmp;
      if (((j & 1) ^ 1) && a[i][j] != t2) ++tmp;
    }
    b[i].push_back(0);
    for (int j = (1); j <= (m); ++j) b[i].push_back((j & 1) ? t1 : t2);
    mn = tmp, swap(t1, t2), tmp = 0;
    for (int j = (1); j <= (m); ++j) {
      if ((j & 1) && a[i][j] != t1) ++tmp;
      if (((j & 1) ^ 1) && a[i][j] != t2) ++tmp;
    }
    if (tmp < mn)
      for (int j = (1); j <= (m); ++j) b[i][j] = ((j & 1) ? t1 : t2);
  }
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = (1); i <= (n); ++i) {
    scanf("%s", s + 1);
    a[i].push_back(0);
    for (int j = (1); j <= (m); ++j) {
      if (s[j] == 'A') a[i].push_back(1);
      if (s[j] == 'C') a[i].push_back(2);
      if (s[j] == 'G') a[i].push_back(3);
      if (s[j] == 'T') a[i].push_back(4);
    }
  }
  for (int i = (1); i <= (m); ++i) {
    b[i].push_back(0);
    for (int j = (1); j <= (n); ++j) b[i].push_back(a[j][i]);
  }
  int ans1 = n * m + 1, ans2 = n * m + 1, c1, c2, d1, d2;
  for (int i = (1); i <= (4); ++i)
    for (int j = (1); j <= (i - 1); ++j) {
      int tmp = calc(i, j, n, m, a);
      if (tmp < ans1) ans1 = tmp, c1 = i, c2 = j;
    }
  for (int i = (1); i <= (4); ++i)
    for (int j = (1); j <= (i - 1); ++j) {
      int tmp = calc(i, j, m, n, b);
      if (tmp < ans2) ans2 = tmp, d1 = i, d2 = j;
    }
  if (ans1 < ans2)
    otp(c1, c2, n, m, a, d);
  else {
    otp(d1, d2, m, n, b, c);
    for (int i = (1); i <= (n); ++i) {
      d[i].push_back(0);
      for (int j = (1); j <= (m); ++j) d[i].push_back(c[j][i]);
    }
  }
  for (int i = (1); i <= (n); ++i) {
    for (int j = (1); j <= (m); ++j) {
      if (d[i][j] == 1) putchar('A');
      if (d[i][j] == 2) putchar('C');
      if (d[i][j] == 3) putchar('G');
      if (d[i][j] == 4) putchar('T');
    }
    puts("");
  }
  return 0;
}
