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>
int n, m, i, j, ans = 0x7fffffff, l;
struct table {
  int mem[300005];
  inline char get(int i, int j) { return mem[i * m + j]; }
  inline void cg(int i, int j, char k) { mem[i * m + j] = k; }
} num, ppt;
inline int min(int a, int b) { return a < b ? a : b; }
inline void MIN(int b, int p) {
  if (ans > b) ans = b, l = p;
}
int chk1(const char* c1, const char* c2) {
  int ret = 0, mn1, mn2;
  for (i = 0; i < m; i++) {
    for (mn1 = mn2 = j = 0; j < n; j++) {
      if (num.get(j, i) != (i & 1 ? c1 : c2)[j & 1]) mn1++;
      if (num.get(j, i) != (i & 1 ? c1 : c2)[(j & 1) ^ 1]) mn2++;
    }
    ret += min(mn1, mn2);
  }
  return ret;
}
int chk2(const char* c1, const char* c2) {
  int ret = 0, mn1, mn2;
  for (i = 0; i < n; i++) {
    for (mn1 = mn2 = j = 0; j < m; j++) {
      if (num.get(i, j) != (i & 1 ? c1 : c2)[j & 1]) mn1++;
      if (num.get(i, j) != (i & 1 ? c1 : c2)[(j & 1) ^ 1]) mn2++;
    }
    ret += min(mn1, mn2);
  }
  return ret;
}
inline void print1(const char* c1, const char* c2) {
  int mn1, mn2;
  for (i = 0; i < m; i++) {
    for (mn1 = mn2 = j = 0; j < n; j++) {
      if (num.get(j, i) != (i & 1 ? c1 : c2)[j & 1]) mn1++;
      if (num.get(j, i) != (i & 1 ? c1 : c2)[(j & 1) ^ 1]) mn2++;
    }
    for (j = 0; j < n; j++)
      ppt.cg(j, i, (i & 1 ? c1 : c2)[(j & 1) ^ (mn1 > mn2 ? 1 : 0)]);
  }
}
inline void print2(const char* c1, const char* c2) {
  int mn1, mn2;
  for (i = 0; i < n; i++) {
    for (mn1 = mn2 = j = 0; j < m; j++) {
      if (num.get(i, j) != (i & 1 ? c1 : c2)[j & 1]) mn1++;
      if (num.get(i, j) != (i & 1 ? c1 : c2)[(j & 1) ^ 1]) mn2++;
    }
    for (j = 0; j < m; j++)
      ppt.cg(i, j, (i & 1 ? c1 : c2)[(j & 1) ^ (mn1 > mn2 ? 1 : 0)]);
  }
}
int main() {
  for (scanf("%d%d", &n, &m), i = 0; i < n; i++)
    for (j = 0; j < m; j++)
      while (num.get(i, j) > 'Z' || num.get(i, j) < 'A')
        num.cg(i, j, getchar());
  MIN(chk1("AG", "CT"), 0);
  MIN(chk1("AC", "GT"), 1);
  MIN(chk1("AT", "CG"), 2);
  MIN(chk1("GC", "AT"), 3);
  MIN(chk1("GT", "AC"), 4);
  MIN(chk1("CT", "AG"), 5);
  MIN(chk2("AG", "CT"), 6);
  MIN(chk2("AC", "GT"), 7);
  MIN(chk2("AT", "CG"), 8);
  MIN(chk2("GC", "AT"), 9);
  MIN(chk2("GT", "AC"), 10);
  MIN(chk2("CT", "AG"), 11);
  switch (l) {
    case 0: {
      print1("AG", "CT");
      break;
    }
    case 1: {
      print1("AC", "GT");
      break;
    }
    case 2: {
      print1("AT", "CG");
      break;
    }
    case 3: {
      print1("GC", "AT");
      break;
    }
    case 4: {
      print1("GT", "AC");
      break;
    }
    case 5: {
      print1("CT", "AG");
      break;
    }
    case 6: {
      print2("AG", "CT");
      break;
    }
    case 7: {
      print2("AC", "GT");
      break;
    }
    case 8: {
      print2("AT", "CG");
      break;
    }
    case 9: {
      print2("GC", "AT");
      break;
    }
    case 10: {
      print2("GT", "AC");
      break;
    }
    case 11: {
      print2("CT", "AG");
      break;
    }
  }
  for (i = 0; i < n; i++, putchar('\n'))
    for (j = 0; j < m; j++) putchar(ppt.get(i, j));
  return 0;
}
