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;
inline int Read() {
  int ret = 0, flag = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') flag = -1;
    ch = getchar();
  }
  while ('0' <= ch && ch <= '9') {
    ret = ret * 10 + (ch - '0');
    ch = getchar();
  }
  return ret * flag;
}
const int maxn = 3e5 + 7;
vector<int> row[maxn];
char Str[maxn];
int n, m, ans = maxn;
int rcd[5], sta;
int ChangeChar(char key) {
  if (key == 'A')
    return 1;
  else if (key == 'G')
    return 2;
  else if (key == 'C')
    return 3;
  else
    return 4;
}
char ChangeNum(int key) {
  if (key == 1)
    return 'A';
  else if (key == 2)
    return 'G';
  else if (key == 3)
    return 'C';
  else
    return 'T';
}
void Check(int step, int s1, int s2, int s3, int s4, int k) {
  if (step >= ans) return;
  rcd[1] = s1, rcd[2] = s2;
  rcd[3] = s3, rcd[4] = s4;
  sta = k, ans = step;
}
void Work(int s1, int s2, int s3, int s4) {
  int tmp = 0, tmp1, tmp2;
  int k1 = s1, k2 = s2, k3 = s3, k4 = s4;
  for (int i = 1; i <= n; i++) {
    tmp1 = tmp2 = 0;
    for (int j = 1; j <= m; j++) {
      if (row[i][j] != s1) tmp1++;
      if (row[i][j] != s2) tmp2++;
      swap(s1, s2);
    }
    tmp += min(tmp1, tmp2);
    swap(s1, s3);
    swap(s2, s4);
  }
  Check(tmp, k1, k2, k3, k4, 0);
  tmp = 0, s1 = k1, s2 = k2, s3 = k3, s4 = k4;
  for (int j = 1; j <= m; j++) {
    tmp1 = tmp2 = 0;
    for (int i = 1; i <= n; i++) {
      if (row[i][j] != s1) tmp1++;
      if (row[i][j] != s2) tmp2++;
      swap(s1, s2);
    }
    tmp += min(tmp1, tmp2);
    swap(s1, s3);
    swap(s2, s4);
  }
  Check(tmp, k1, k2, k3, k4, 1);
}
int main() {
  n = Read(), m = Read();
  for (int i = 1; i <= n; i++) {
    scanf("%s", Str + 1);
    row[i].push_back(0);
    for (int j = 1; j <= m; j++) row[i].push_back(ChangeChar(Str[j]));
  }
  Work(1, 2, 3, 4);
  Work(1, 3, 2, 4);
  Work(1, 4, 2, 3);
  Work(2, 3, 1, 4);
  Work(2, 4, 1, 3);
  Work(3, 4, 1, 2);
  if (!sta) {
    for (int i = 1; i <= n; i++) {
      int tmp1 = 0, tmp2 = 0, f1 = rcd[1], f2 = rcd[2];
      for (int j = 1; j <= m; j++) {
        if (row[i][j] != rcd[1]) tmp1++;
        if (row[i][j] != rcd[2]) tmp2++;
        swap(rcd[1], rcd[2]);
      }
      if (tmp2 < tmp1) swap(f1, f2);
      for (int j = 1; j <= m; j++) {
        if (j & 1)
          row[i][j] = f1;
        else
          row[i][j] = f2;
      }
      swap(rcd[1], rcd[3]);
      swap(rcd[2], rcd[4]);
    }
  } else {
    for (int j = 1; j <= m; j++) {
      int tmp1 = 0, tmp2 = 0, f1 = rcd[1], f2 = rcd[2];
      for (int i = 1; i <= n; i++) {
        if (row[i][j] != rcd[1]) tmp1++;
        if (row[i][j] != rcd[2]) tmp2++;
        swap(rcd[1], rcd[2]);
      }
      if (tmp1 > tmp2) swap(f1, f2);
      for (int i = 1; i <= n; i++) {
        if (i & 1)
          row[i][j] = f1;
        else
          row[i][j] = f2;
      }
      swap(rcd[1], rcd[3]);
      swap(rcd[2], rcd[4]);
    }
  }
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      putchar(ChangeNum(row[i][j]));
    }
    putchar('\n');
  }
  return 0;
}
