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 long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; }
inline long long lcm(long long a, long long b) { return a / gcd(a, b) * b; }
int month[15] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
int dir[8][2] = {{-1, 0},  {1, 0}, {0, -1}, {0, 1},
                 {-1, -1}, {1, 1}, {1, -1}, {-1, 1}};
const int MAXN = 3e5 + 5;
const int INF = 1 << 30;
const long long mod = 1e9 + 7;
const double eps = 1e-8;
const long long inff = 0x3f3f3f3f3f3f3f3f;
int n, m, ans = mod, s[3];
char c, d[5] = {'A', 'G', 'C', 'T'};
vector<char> q[MAXN];
void solve(char s1, char s2, int t) {
  char s3 = ' ', s4;
  for (int i = 0; i <= 3; i++) {
    if (d[i] != s1 && d[i] != s2 && s3 == ' ') s3 = d[i];
    if (d[i] != s1 && d[i] != s2 && s3 != ' ') s4 = d[i];
  }
  int sum = 0;
  if (t == 1) {
    for (int i = 0; i <= n - 1; i++) {
      int cn[3] = {0, 0};
      char cc[3];
      if (i % 2)
        cc[0] = s1, cc[1] = s2;
      else
        cc[0] = s3, cc[1] = s4;
      for (int j = 0; j <= m - 1; j++) {
        int k = j % 2, kk = !k;
        if (q[i][j] != cc[k]) cn[0]++;
        if (q[i][j] != cc[kk]) cn[1]++;
      }
      sum += min(cn[0], cn[1]);
    }
  }
  if (t == 2) {
    for (int i = 0; i <= m - 1; i++) {
      int cn[3] = {0, 0};
      char cc[3];
      if (i % 2)
        cc[0] = s1, cc[1] = s2;
      else
        cc[0] = s3, cc[1] = s4;
      for (int j = 0; j <= n - 1; j++) {
        int k = j % 2, kk = !k;
        if (q[j][i] != cc[k]) cn[0]++;
        if (q[j][i] != cc[kk]) cn[1]++;
      }
      sum += min(cn[0], cn[1]);
    }
  }
  if (t != 0) {
    if (sum < ans) ans = sum, s[0] = s1, s[1] = s2, s[2] = t;
  } else {
    t = s[2];
    if (t == 1) {
      for (int i = 0; i <= n - 1; i++) {
        int cn[3] = {0, 0};
        char cc[3];
        if (i % 2)
          cc[0] = s1, cc[1] = s2;
        else
          cc[0] = s3, cc[1] = s4;
        for (int j = 0; j <= m - 1; j++) {
          int k = j % 2, kk = !k;
          if (q[i][j] != cc[k]) cn[0]++;
          if (q[i][j] != cc[kk]) cn[1]++;
        }
        if (cn[0] < cn[1]) {
          for (int j = 0; j <= m - 1; j++) {
            int k = j % 2;
            q[i][j] = cc[k];
          }
        } else {
          for (int j = 0; j <= m - 1; j++) {
            int k = !(j % 2);
            q[i][j] = cc[k];
          }
        }
      }
    }
    if (t == 2) {
      for (int i = 0; i <= m - 1; i++) {
        int cn[3] = {0, 0};
        char cc[3];
        if (i % 2)
          cc[0] = s1, cc[1] = s2;
        else
          cc[0] = s3, cc[1] = s4;
        for (int j = 0; j <= n - 1; j++) {
          int k = j % 2, kk = !k;
          if (q[j][i] != cc[k]) cn[0]++;
          if (q[j][i] != cc[kk]) cn[1]++;
        }
        if (cn[0] < cn[1]) {
          for (int j = 0; j <= n - 1; j++) {
            int k = j % 2;
            q[j][i] = cc[k];
          }
        } else {
          for (int j = 0; j <= n - 1; j++) {
            int k = !(j % 2);
            q[j][i] = cc[k];
          }
        }
      }
    }
    for (int i = 0; i <= n - 1; i++) {
      for (int j = 0; j <= m - 1; j++) printf("%c", q[i][j]);
      printf("\n");
    }
  }
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 0; i <= n - 1; i++) {
    getchar();
    for (int j = 1; j <= m; j++) {
      scanf("%c", &c);
      q[i].push_back(c);
    }
  }
  for (int i = 0; i <= 2; i++)
    for (int j = i + 1; j <= 3; j++) solve(d[i], d[j], 1);
  for (int i = 0; i <= 2; i++)
    for (int j = i + 1; j <= 3; j++) solve(d[i], d[j], 2);
  solve(s[0], s[1], 0);
}
