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;
const int MAXN = 300050;
int n, m;
char ss[MAXN];
string G[MAXN], W[MAXN], DNA = "ACGT";
void getstring(string &s) {
  scanf(" %s", ss);
  s = ss;
}
int to_id(char ch) {
  if (ch == 'A') return 0;
  if (ch == 'C') return 1;
  if (ch == 'G') return 2;
  return 3;
}
char ch(int c) { return DNA[c]; }
int paint_row(int i, char ch1, char ch2) {
  int match = 0;
  for (int j = (0); j < (int)(m); j++) {
    W[i][j] = (j % 2) ? ch1 : ch2;
    if (G[i][j] == W[i][j]) match++;
  }
  return match;
}
int paint_col(int j, char ch1, char ch2) {
  int match = 0;
  for (int i = (0); i < (int)(n); i++) {
    W[i][j] = (i % 2) ? ch1 : ch2;
    if (G[i][j] == W[i][j]) match++;
  }
  return match;
}
int solve_row(int c1, int c2, int c3, int c4) {
  char ch1 = ch(c1);
  char ch2 = ch(c2);
  char ch3 = ch(c3);
  char ch4 = ch(c4);
  int ans = 0;
  for (int i = (0); i < (int)(n); i++) {
    if (paint_row(i, ch1, ch2) > paint_row(i, ch2, ch1)) {
      ans += paint_row(i, ch1, ch2);
    } else {
      ans += paint_row(i, ch2, ch1);
    }
    swap(ch1, ch3);
    swap(ch2, ch4);
  }
  return ans;
}
int solve_col(int c1, int c2, int c3, int c4) {
  char ch1 = ch(c1);
  char ch2 = ch(c2);
  char ch3 = ch(c3);
  char ch4 = ch(c4);
  int ans = 0;
  for (int j = (0); j < (int)(m); j++) {
    if (paint_col(j, ch1, ch2) > paint_col(j, ch2, ch1)) {
      ans += paint_col(j, ch1, ch2);
    } else {
      ans += paint_col(j, ch2, ch1);
    }
    swap(ch1, ch3);
    swap(ch2, ch4);
  }
  return ans;
}
int main() {
  while (scanf("%d %d", &n, &m) >= 1) {
    for (int i = (0); i < (int)(n); i++) {
      getstring(G[i]);
      W[i] = G[i];
    }
    int best = -1;
    vector<int> ans;
    bool row = false;
    vector<int> V = {0, 1, 2, 3};
    do {
      int cand = solve_row(V[0], V[1], V[2], V[3]);
      if (cand > best) {
        best = cand;
        ans = V;
        row = true;
      }
      cand = solve_col(V[0], V[1], V[2], V[3]);
      if (cand > best) {
        best = cand;
        ans = V;
        row = false;
      }
    } while (next_permutation(V.begin(), V.end()));
    if (row)
      solve_row(ans[0], ans[1], ans[2], ans[3]);
    else
      solve_col(ans[0], ans[1], ans[2], ans[3]);
    for (int i = (0); i < (int)(n); i++) {
      printf("%s\n", W[i].c_str());
    }
  }
  return 0;
}
