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>
const int MAXC = 4;
const int MAXN = 3e5 + 5;
const char* acgt = "ACGT";
char buff[MAXN];
std::string ans[MAXN], s[MAXN];
int m, n;
std::string dyn;
int best;
std::string ret;
bool cr;
void augment(int sum, bool flag) {
  if (sum >= best) return;
  best = sum;
  ret = dyn;
  cr = flag;
}
void format(int a, int end, bool second, int row) {
  for (int b = 0; b < end; ++b) {
    ans[(row < 0) ? b : row] += dyn[(a & 1) * 2 + ((b & 1) ^ second)];
  }
}
void solve_cols(bool out) {
  int sum = 0;
  for (int j = 0; j < m; ++j) {
    int cnt[2]{};
    for (int i = 0; i < n; ++i) {
      if (s[i][j] != dyn[(j & 1) * 2 + (i & 1)]) ++cnt[0];
      if (s[i][j] != dyn[(j & 1) * 2 + ((i & 1) ^ 1)]) ++cnt[1];
    }
    sum += std::min(cnt[0], cnt[1]);
    if (out) format(j, n, (cnt[1] <= cnt[0]), -1);
  }
  augment(sum, true);
}
void solve_rows(bool out) {
  int sum = 0;
  for (int i = 0; i < n; ++i) {
    int cnt[2]{};
    for (int j = 0; j < m; ++j) {
      if (s[i][j] != dyn[(i & 1) * 2 + (j & 1)]) ++cnt[0];
      if (s[i][j] != dyn[(i & 1) * 2 + ((j & 1) ^ 1)]) ++cnt[1];
    }
    sum += std::min(cnt[0], cnt[1]);
    if (out) format(i, m, (cnt[1] <= cnt[0]), i);
  }
  augment(sum, false);
}
int main() {
  scanf(" %d%d", &n, &m);
  for (int i = 0; i < n; ++i) {
    scanf(" %s", buff);
    s[i] = buff;
  }
  best = m * n;
  dyn = ret = acgt;
  cr = false;
  do {
    solve_cols(false);
    solve_rows(false);
  } while (std::next_permutation((dyn).begin(), (dyn).end()));
  dyn = ret;
  if (cr) {
    solve_cols(true);
  } else {
    solve_rows(true);
  }
  for (int i = 0; i < n; ++i) {
    puts(ans[i].c_str());
  }
  return 0;
}
