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, Max;
const char let[9] = "ATCG";
char s[300000 + 5], t[300000 + 5], ans[300000 + 5];
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 0; i < n; i++) scanf("%s", s + i * m);
  for (int a = 0; a < 4; a++)
    for (int b = 0; b < 4; b++)
      if (a != b) {
        char x1 = let[a], x2 = let[b], y1, y2;
        for (int c = 0; c < 4; c++)
          if (c != a && c != b) {
            y1 = let[c];
            break;
          }
        for (int c = 3; c >= 0; c--)
          if (c != a && c != b) {
            y2 = let[c];
            break;
          }
        int tot_r = 0, tot_c = 0;
        for (int i = 0; i < n; i++) {
          char z0 = (i % 2 == 0 ? x1 : y1);
          char z1 = (i % 2 == 0 ? x2 : y2);
          int cnt_0 = 0, cnt_1 = 0;
          for (int j = 0; j < m; j++) {
            if ((j % 2 == 0 && s[i * m + j] == z0) ||
                (j % 2 == 1 && s[i * m + j] == z1))
              cnt_0++;
            if ((j % 2 == 0 && s[i * m + j] == z1) ||
                (j % 2 == 1 && s[i * m + j] == z0))
              cnt_1++;
          }
          if (cnt_0 >= cnt_1) {
            tot_r += cnt_0;
            for (int j = 0; j < m; j++) t[i * m + j] = j % 2 == 0 ? z0 : z1;
          } else {
            tot_r += cnt_1;
            for (int j = 0; j < m; j++) t[i * m + j] = j % 2 == 0 ? z1 : z0;
          }
        }
        if (tot_r > Max) {
          for (int i = 0; i < n * m; i++) ans[i] = t[i];
          Max = tot_r;
        }
        for (int j = 0; j < m; j++) {
          char z0 = (j % 2 == 0 ? x1 : y1);
          char z1 = (j % 2 == 0 ? x2 : y2);
          int cnt_0 = 0, cnt_1 = 0;
          for (int i = 0; i < n; i++) {
            if ((i % 2 == 0 && s[i * m + j] == z0) ||
                (i % 2 == 1 && s[i * m + j] == z1))
              cnt_0++;
            if ((i % 2 == 0 && s[i * m + j] == z1) ||
                (i % 2 == 1 && s[i * m + j] == z0))
              cnt_1++;
          }
          if (cnt_0 >= cnt_1) {
            tot_c += cnt_0;
            for (int i = 0; i < n; i++) t[i * m + j] = i % 2 == 0 ? z0 : z1;
          } else {
            tot_c += cnt_1;
            for (int i = 0; i < n; i++) t[i * m + j] = i % 2 == 0 ? z1 : z0;
          }
        }
        if (tot_c > Max) {
          for (int i = 0; i < n * m; i++) ans[i] = t[i];
          Max = tot_c;
        }
      }
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) putchar(ans[i * m + j]);
    putchar('\n');
  }
  return 0;
}
