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;
template <class T, class T2>
inline int chkmax(T &x, const T2 &y) {
  return x < y ? x = y, 1 : 0;
}
template <class T, class T2>
inline int chkmin(T &x, const T2 &y) {
  return x > y ? x = y, 1 : 0;
}
const int MAXN = (int)3e5 + 42;
using table = vector<string>;
int n, m;
table s;
void read() {
  cin >> n >> m;
  s.resize(n);
  for (int i = 0; i < n; i++) cin >> s[i];
}
string Sg = {'A', 'G', 'C', 'T'};
pair<int, table> answer;
int dp[MAXN][4][4];
pair<int, int> best[MAXN][4][4];
int rec1(int row, int last1, int last2) {
  if (row == n) return 0;
  int &memo = dp[row][last1][last2];
  if (memo != -1) return memo;
  vector<int> li;
  for (int i = 0; i < 4; i++)
    if (row == 0 || (i != last1 && i != last2)) li.push_back(i);
  for (int i = 0; i < ((int)li.size()); i++)
    for (int j = 0; j < ((int)li.size()); j++)
      if (i != j) {
        int cost = 0;
        for (int c = 0; c < m; c++) {
          if (!(c & 1))
            if (Sg[li[i]] == s[row][c]) cost++;
          if (c & 1)
            if (Sg[li[j]] == s[row][c]) cost++;
        }
        if (chkmax(memo, cost + rec1(row + 1, li[i], li[j])))
          best[row][last1][last2] = {li[i], li[j]};
      }
  return memo;
}
int rec2(int row, int last1, int last2) {
  if (row == m) return 0;
  int &memo = dp[row][last1][last2];
  if (memo != -1) return memo;
  vector<int> li;
  for (int i = 0; i < 4; i++)
    if (row == 0 || (i != last1 && i != last2)) li.push_back(i);
  for (int i = 0; i < ((int)li.size()); i++)
    for (int j = 0; j < ((int)li.size()); j++)
      if (i != j) {
        int cost = 0;
        for (int c = 0; c < n; c++) {
          if (!(c & 1))
            if (Sg[li[i]] == s[c][row]) cost++;
          if (c & 1)
            if (Sg[li[j]] == s[c][row]) cost++;
        }
        if (chkmax(memo, cost + rec2(row + 1, li[i], li[j])))
          best[row][last1][last2] = {li[i], li[j]};
      }
  return memo;
}
void solve1() {
  memset(dp, -1, sizeof(dp));
  int best_ans = rec1(0, 0, 0);
  int row = 0, last1 = 0, last2 = 0;
  table answer;
  answer.assign(n, string(m, ' '));
  while (row < n) {
    rec1(row, last1, last2);
    int nw_last1 = best[row][last1][last2].first,
        nw_last2 = best[row][last1][last2].second;
    last1 = nw_last1, last2 = nw_last2;
    for (int c = 0; c < m; c++)
      if (c & 1)
        answer[row][c] = Sg[last2];
      else
        answer[row][c] = Sg[last1];
    row++;
  }
  chkmax(::answer, make_pair(best_ans, answer));
}
void solve2() {
  memset(dp, -1, sizeof(dp));
  int best_ans = rec2(0, 0, 0);
  int row = 0, last1 = 0, last2 = 0;
  table answer;
  answer.assign(n, string(m, ' '));
  while (row < m) {
    rec2(row, last1, last2);
    int nw_last1 = best[row][last1][last2].first,
        nw_last2 = best[row][last1][last2].second;
    last1 = nw_last1, last2 = nw_last2;
    for (int c = 0; c < n; c++)
      if (c & 1)
        answer[c][row] = Sg[last2];
      else
        answer[c][row] = Sg[last1];
    row++;
  }
  chkmax(::answer, make_pair(best_ans, answer));
}
void solve() {
  answer.first = -1;
  solve1();
  solve2();
  for (int i = 0; i < n; i++) cout << answer.second[i] << '\n';
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  read();
  solve();
  return 0;
}
