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 n, m, mn, tmp, t1, t2, side;
char r, ch[5], ans[5];
vector<char> v[300005], a[300005];
int main() {
  scanf("%d%d", &n, &m);
  mn = n * m;
  ch[1] = 'A';
  ch[2] = 'C';
  ch[3] = 'G';
  ch[4] = 'T';
  for (int i = 1; i <= n; i++) {
    scanf("\n");
    v[i].push_back(' ');
    for (int j = 1; j <= m; j++) {
      scanf("%c", &r);
      v[i].push_back(r);
    }
  }
  do {
    tmp = 0;
    for (int i = 1; i <= m; i++) {
      t1 = t2 = 0;
      if (i % 2)
        for (int j = 1; j <= n; j++) {
          if (j % 2) {
            if (v[j][i] != ch[1]) t1++;
            if (v[j][i] != ch[2]) t2++;
          } else {
            if (v[j][i] != ch[2]) t1++;
            if (v[j][i] != ch[1]) t2++;
          }
        }
      else
        for (int j = 1; j <= n; j++) {
          if (j % 2) {
            if (v[j][i] != ch[3]) t1++;
            if (v[j][i] != ch[4]) t2++;
          } else {
            if (v[j][i] != ch[4]) t1++;
            if (v[j][i] != ch[3]) t2++;
          }
        }
      tmp += min(t1, t2);
    }
    if (tmp < mn) {
      mn = tmp;
      for (int i = 1; i <= 4; i++) {
        ans[i] = ch[i];
      }
      side = 1;
    }
    tmp = 0;
    for (int i = 1; i <= n; i++) {
      t1 = t2 = 0;
      if (i % 2)
        for (int j = 1; j <= m; j++) {
          if (j % 2) {
            if (v[i][j] != ch[1]) t1++;
            if (v[i][j] != ch[2]) t2++;
          } else {
            if (v[i][j] != ch[2]) t1++;
            if (v[i][j] != ch[1]) t2++;
          }
        }
      else
        for (int j = 1; j <= m; j++) {
          if (j % 2) {
            if (v[i][j] != ch[3]) t1++;
            if (v[i][j] != ch[4]) t2++;
          } else {
            if (v[i][j] != ch[4]) t1++;
            if (v[i][j] != ch[3]) t2++;
          }
        }
      tmp += min(t1, t2);
    }
    if (tmp < mn) {
      mn = tmp;
      for (int i = 1; i <= 4; i++) {
        ans[i] = ch[i];
      }
      side = 0;
    }
  } while (next_permutation(ch + 1, ch + 5));
  for (int i = 1; i <= n; i++) {
    a[i].push_back(' ');
  }
  if (side) {
    for (int i = 1; i <= m; i++) {
      t1 = t2 = 0;
      if (i % 2)
        for (int j = 1; j <= n; j++) {
          if (j % 2) {
            if (v[j][i] != ans[1]) t1++;
            if (v[j][i] != ans[2]) t2++;
          } else {
            if (v[j][i] != ans[2]) t1++;
            if (v[j][i] != ans[1]) t2++;
          }
        }
      else
        for (int j = 1; j <= n; j++) {
          if (j % 2) {
            if (v[j][i] != ans[3]) t1++;
            if (v[j][i] != ans[4]) t2++;
          } else {
            if (v[j][i] != ans[4]) t1++;
            if (v[j][i] != ans[3]) t2++;
          }
        }
      if (t1 < t2) {
        for (int j = 1; j <= n; j++) {
          if (i % 2) {
            if (j % 2)
              a[j].push_back(ans[1]);
            else
              a[j].push_back(ans[2]);
          } else {
            if (j % 2)
              a[j].push_back(ans[3]);
            else
              a[j].push_back(ans[4]);
          }
        }
      } else {
        for (int j = 1; j <= n; j++) {
          if (i % 2) {
            if (j % 2)
              a[j].push_back(ans[2]);
            else
              a[j].push_back(ans[1]);
          } else {
            if (j % 2)
              a[j].push_back(ans[4]);
            else
              a[j].push_back(ans[3]);
          }
        }
      }
    }
  } else {
    for (int i = 1; i <= n; i++) {
      t1 = t2 = 0;
      if (i % 2)
        for (int j = 1; j <= m; j++) {
          if (j % 2) {
            if (v[i][j] != ans[1]) t1++;
            if (v[i][j] != ans[2]) t2++;
          } else {
            if (v[i][j] != ans[2]) t1++;
            if (v[i][j] != ans[1]) t2++;
          }
        }
      else
        for (int j = 1; j <= m; j++) {
          if (j % 2) {
            if (v[i][j] != ans[3]) t1++;
            if (v[i][j] != ans[4]) t2++;
          } else {
            if (v[i][j] != ans[4]) t1++;
            if (v[i][j] != ans[3]) t2++;
          }
        }
      if (t1 < t2) {
        for (int j = 1; j <= m; j++) {
          if (i % 2) {
            if (j % 2)
              a[i].push_back(ans[1]);
            else
              a[i].push_back(ans[2]);
          } else {
            if (j % 2)
              a[i].push_back(ans[3]);
            else
              a[i].push_back(ans[4]);
          }
        }
      } else {
        for (int j = 1; j <= m; j++) {
          if (i % 2) {
            if (j % 2)
              a[i].push_back(ans[2]);
            else
              a[i].push_back(ans[1]);
          } else {
            if (j % 2)
              a[i].push_back(ans[4]);
            else
              a[i].push_back(ans[3]);
          }
        }
      }
    }
  }
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      printf("%c", a[i][j]);
    }
    printf("\n");
  }
  return 0;
}
