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;
int ans;
int p[300100];
int b[300100], c[300100];
int c2i[300];
char i2c[300];
int used[10];
char s[300100];
void Compute(int u, int v) {
  int x[3][3];
  int cost[2], current, phase;
  x[0][0] = u;
  x[0][1] = v;
  for (x[1][0] = 0; x[1][0] < 4; ++x[1][0])
    if (x[1][0] != u && x[1][0] != v) break;
  x[1][1] = 6 - u - v - x[1][0];
  current = 0;
  for (int i = 0; i < n; ++i) {
    cost[0] = cost[1] = 0;
    for (int j = 0; j < m; ++j) {
      if (b[i * m + j] != x[i & 1][0 ^ (j & 1)]) cost[0] += 1;
      if (b[i * m + j] != x[i & 1][1 ^ (j & 1)]) cost[1] += 1;
    }
    phase = 0;
    if (cost[1] < cost[0]) phase = 1;
    current += cost[phase];
    for (int j = 0; j < m; ++j) {
      c[i * m + j] = x[i & 1][phase ^ (j & 1)];
    }
  }
  if (current < ans) {
    ans = current;
    for (int i = 0; i < n * m; ++i) p[i] = c[i];
  }
  current = 0;
  for (int j = 0; j < m; ++j) {
    cost[0] = cost[1] = 0;
    for (int i = 0; i < n; ++i) {
      if (b[i * m + j] != x[j & 1][(i & 1) ^ 0]) cost[0] += 1;
      if (b[i * m + j] != x[j & 1][(i & 1) ^ 1]) cost[1] += 1;
    }
    phase = 0;
    if (cost[1] < cost[0]) phase = 1;
    current += cost[phase];
    for (int i = 0; i < n; ++i) {
      c[i * m + j] = x[j & 1][(i & 1) ^ phase];
    }
  }
  if (current < ans) {
    ans = current;
    for (int i = 0; i < n * m; ++i) p[i] = c[i];
  }
}
int main() {
  scanf("%d %d", &n, &m);
  ans = n * m + 1;
  i2c[0] = 'A';
  i2c[1] = 'C';
  i2c[2] = 'G';
  i2c[3] = 'T';
  for (int i = 0; i < 4; ++i) c2i[i2c[i]] = i;
  for (int i = 0; i < n; ++i) {
    scanf("%s", s);
    for (int j = 0; j < m; ++j) b[i * m + j] = c2i[s[j]];
  }
  for (int i = 0; i < 4; ++i)
    for (int j = i + 1; j < 4; ++j) Compute(i, j);
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < m; ++j) printf("%c", i2c[p[i * m + j]]);
    printf("\n");
  }
  return 0;
}
