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;
const int Maxn = 300005;
char choose[][2] = {{0, 0},     {'A', 'G'}, {'A', 'C'}, {'A', 'T'},
                    {'C', 'T'}, {'G', 'T'}, {'C', 'G'}};
int pos[3][Maxn][7], n, now[3], m, way1, way2, tot[3][Maxn];
string str[Maxn], T[Maxn];
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) cin >> str[i];
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= 6; j++) {
      now[1] = now[2] = 0;
      for (int k = 1; k <= m; k++) {
        now[1] += choose[(j + (i & 1) * 3 - 1) % 6 + 1][k & 1] != str[i][k - 1];
        now[2] +=
            choose[(j + (i & 1) * 3 - 1) % 6 + 1][!(k & 1)] != str[i][k - 1];
      }
      pos[0][i][j] = now[1] < now[2] ? 1 : 2;
      tot[0][j] += min(now[1], now[2]);
    }
  }
  for (int i = 1; i <= m; i++) {
    for (int j = 1; j <= 6; j++) {
      now[1] = now[2] = 0;
      for (int k = 1; k <= n; k++) {
        now[1] += choose[(j + (i & 1) * 3 - 1) % 6 + 1][k & 1] != str[k][i - 1];
        now[2] +=
            choose[(j + (i & 1) * 3 - 1) % 6 + 1][!(k & 1)] != str[k][i - 1];
      }
      pos[1][i][j] = now[1] < now[2] ? 1 : 2;
      tot[1][j] += min(now[1], now[2]);
    }
  }
  int ans = 0x3f3f3f3f;
  for (int i = 0; i <= 1; i++)
    for (int j = 1; j <= 6; j++)
      if (tot[i][j] < ans) ans = tot[i][j], way1 = i, way2 = j;
  if (!way1) {
    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= m; j++)
        printf("%c", choose[(way2 + (i & 1) * 3 - 1) % 6 + 1]
                           [(j & 1) != (pos[0][i][way2] - 1)]);
      printf("\n");
    }
  } else {
    for (int i = 1; i <= m; i++)
      for (int j = 1; j <= n; j++)
        T[j] += choose[(way2 + (i & 1) * 3 - 1) % 6 + 1]
                      [(j & 1) != (pos[1][i][way2] - 1)];
    for (int i = 1; i <= n; i++) cout << T[i] << endl;
  }
  return 0;
}
