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;
string mp[300005], smp[300005], fin[300005];
int ans, sum, n, m;
string s[5];
int cnt[300005][2][5];
int change[300];
void calc(int a, int b, int c, int d) {
  for (int i = 0; i < n; i++) smp[i] = "";
  for (int j = 0; j < m; j++) {
    if (j % 2 == 0) {
      if (cnt[j][0][a] + cnt[j][1][b] > cnt[j][0][b] + cnt[j][1][a])
        smp[0] += s[a], smp[1] += s[b];
      else
        smp[0] += s[b], smp[1] += s[a];
    } else {
      if (cnt[j][0][c] + cnt[j][1][d] > cnt[j][0][d] + cnt[j][1][c])
        smp[0] += s[c], smp[1] += s[d];
      else
        smp[0] += s[d], smp[1] += s[c];
    }
  }
  for (int i = 2; i < n; i++) {
    smp[i] = smp[i - 2];
  }
  int sum = 0;
  for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++)
      if (mp[i][j] != smp[i][j]) sum++;
  if (sum < ans) {
    for (int i = 0; i < n; i++) fin[i] = smp[i];
    ans = sum;
  }
}
void calc2(int a, int b, int c, int d) {
  for (int i = 0; i < n; i++) smp[i] = "";
  for (int j = 0; j < n; j++) {
    if (j % 2 == 0) {
      if (cnt[j][0][a] + cnt[j][1][b] > cnt[j][0][b] + cnt[j][1][a])
        smp[j] += s[a], smp[j] += s[b];
      else
        smp[j] += s[b], smp[j] += s[a];
    } else {
      if (cnt[j][0][c] + cnt[j][1][d] > cnt[j][0][d] + cnt[j][1][c])
        smp[j] += s[c], smp[j] += s[d];
      else
        smp[j] += s[d], smp[j] += s[c];
    }
  }
  for (int i = 0; i < n; i++) {
    for (int j = 2; j < m; j++) smp[i] += smp[i][j - 2];
  }
  int sum = 0;
  for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++)
      if (mp[i][j] != smp[i][j]) sum++;
  if (sum < ans) {
    for (int i = 0; i < n; i++) fin[i] = smp[i];
    ans = sum;
  }
}
int main() {
  change['A'] = 1, change['T'] = 2, change['G'] = 3, change['C'] = 4;
  scanf("%d%d", &n, &m);
  for (int i = 0; i < n; i++) {
    cin >> mp[i];
    for (int j = 0; j < m; j++) cnt[j][i % 2][change[mp[i][j]]]++;
  }
  s[1] = s[2] = s[3] = s[4] = "";
  s[1] += "A", s[2] += "T", s[3] += "G", s[4] += "C";
  ans = 1e8;
  int a[5] = {1, 2, 3, 4};
  do {
    calc(a[0], a[1], a[2], a[3]);
  } while (next_permutation(a, a + 4));
  memset(cnt, 0, sizeof(cnt));
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) cnt[i][j % 2][change[mp[i][j]]]++;
  }
  do {
    calc2(a[0], a[1], a[2], a[3]);
  } while (next_permutation(a, a + 4));
  for (int i = 0; i < n; i++) cout << fin[i] << endl;
  return 0;
}
