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;
long long int mod = 1e9 + 7;
double error = 1e-8;
inline long long int MOD(long long int x, long long int m = mod) {
  long long int y = x % m;
  return (y >= 0) ? y : y + m;
}
const int inf = INT_MAX;
const long long int infl = LLONG_MAX;
const int nmax = 3e5 + 10;
int mp[128];
char rev[4] = {'A', 'C', 'G', 'T'};
char mat[2][nmax];
char ans[nmax];
int cnt[2][nmax][2][4];
char best[2][nmax];
int bestperm[2];
char tmp[nmax];
int perm[6][2] = {{0, 1}, {0, 2}, {0, 3}, {1, 2}, {1, 3}, {2, 3}};
void precal(int n, int m, int x) {
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) cnt[x][i][j & 1][mp[mat[x][i * m + j]]]++;
  }
}
int calc(int n, int m, int x) {
  int a = (m + 1) / 2;
  int b = m / 2;
  int ret = inf;
  for (int p = 0; p < 6; p++) {
    int miss = 0;
    for (int i = 0; i < n; i++) {
      int q = (i & 1) ? p : 5 - p;
      int tmp1 = a - cnt[x][i][0][perm[q][0]] + b - cnt[x][i][1][perm[q][1]];
      int tmp2 = a - cnt[x][i][0][perm[q][1]] + b - cnt[x][i][1][perm[q][0]];
      if (tmp1 < tmp2)
        tmp[i] = rev[perm[q][0]], miss += tmp1;
      else
        tmp[i] = rev[perm[q][1]], miss += tmp2;
    }
    if (miss < ret) {
      memcpy(best[x], tmp, sizeof(char) * n);
      ret = miss;
      bestperm[x] = p;
    }
  }
  return ret;
}
void fillup(int n, int m, int x) {
  for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++) {
      int p = (i & 1) ? bestperm[x] : 5 - bestperm[x];
      ans[i * m + j] = (j % 2 == 0) ? mp[best[x][i]]
                                    : perm[p][0] + perm[p][1] - mp[best[x][i]];
    }
}
int main() {
  mp['A'] = 0;
  mp['C'] = 1;
  mp['G'] = 2;
  mp['T'] = 3;
  int n, m;
  scanf("%d %d", &n, &m);
  for (int i = 0; i < n; i++) {
    getchar();
    for (int j = 0; j < m; j++) {
      mat[0][i * m + j] = getchar();
      mat[1][j * n + i] = mat[0][i * m + j];
    }
  }
  precal(n, m, 0);
  precal(m, n, 1);
  int ans1 = calc(n, m, 0);
  int ans2 = calc(m, n, 1);
  if (ans1 < ans2) {
    fillup(n, m, 0);
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) putchar(rev[ans[i * m + j]]);
      puts("");
    }
  } else {
    fillup(m, n, 1);
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) putchar(rev[ans[j * n + i]]);
      if (i != n - 1) puts("");
    }
  }
}
