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;
int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
const int MAXCELLS = 300000;
const char CHARS[4] = {'A', 'C', 'G', 'T'};
int h, w;
char s[MAXCELLS + 1];
char ans[MAXCELLS + 1];
char t[MAXCELLS + 1];
void solve() {
  int best = INT_MAX;
  for (int i = (0); i < (h * w); ++i) ans[i] = '?';
  t[h * w] = ans[h * w] = '\0';
  for (int a = (0); a < (4); ++a)
    for (int b = (a + 1); b < (4); ++b)
      for (int c = (0); c < (4); ++c)
        for (int d = (c + 1); d < (4); ++d) {
          if (c == a || c == b || d == a || d == b) continue;
          for (int x = (0); x < (h); ++x) {
            int u = x % 2 == 0 ? a : c, v = x % 2 == 0 ? b : d;
            int match[2];
            match[0] = match[1] = 0;
            for (int y = (0); y < (w); ++y)
              if (s[x * w + y] == CHARS[u])
                ++match[y % 2];
              else if (s[x * w + y] == CHARS[v])
                ++match[1 - y % 2];
            if (match[1] > match[0]) swap(u, v);
            for (int y = (0); y < (w); ++y)
              t[x * w + y] = y % 2 == 0 ? CHARS[u] : CHARS[v];
          }
          {
            int cur = 0;
            for (int i = (0); i < (h * w); ++i)
              if (s[i] != t[i]) ++cur;
            if (cur < best) {
              best = cur;
              for (int i = (0); i < (h * w); ++i) ans[i] = t[i];
            }
          }
          for (int y = (0); y < (w); ++y) {
            int u = y % 2 == 0 ? a : c, v = y % 2 == 0 ? b : d;
            int match[2];
            match[0] = match[1] = 0;
            for (int x = (0); x < (h); ++x)
              if (s[x * w + y] == CHARS[u])
                ++match[x % 2];
              else if (s[x * w + y] == CHARS[v])
                ++match[1 - x % 2];
            if (match[1] > match[0]) swap(u, v);
            for (int x = (0); x < (h); ++x)
              t[x * w + y] = x % 2 == 0 ? CHARS[u] : CHARS[v];
          }
          {
            int cur = 0;
            for (int i = (0); i < (h * w); ++i)
              if (s[i] != t[i]) ++cur;
            if (cur < best) {
              best = cur;
              for (int i = (0); i < (h * w); ++i) ans[i] = t[i];
            }
          }
        }
}
void run() {
  scanf("%d%d", &h, &w);
  for (int x = (0); x < (h); ++x) scanf("%s", s + x * w);
  solve();
  for (int x = (0); x < (h); ++x) printf("%.*s\n", w, ans + x * w);
}
int main() {
  run();
  return 0;
}
