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;
inline void read(int &sum) {
  char ch = getchar();
  int tf = 0;
  sum = 0;
  while ((ch < '0' || ch > '9') && (ch != '-')) ch = getchar();
  tf = ((ch == '-') && (ch = getchar()));
  while (ch >= '0' && ch <= '9') sum = sum * 10 + (ch - 48), ch = getchar();
  (tf) && (sum = -sum);
}
int n, m;
vector<string> vec;
vector<string> res_vec, res_vec_tmp1, res_vec_tmp2;
string str = "AGCT";
int ans;
void cal(char a, char b, char c, char d) {
  int ans_r = 0;
  for (int i = 0; i < n; i += 2) {
    int tmp_1 = 0;
    for (int j = 0; j < m; j++) {
      if ((j & 1) && vec[i][j] != a) tmp_1++;
      if (!(j & 1) && vec[i][j] != b) tmp_1++;
    }
    int tmp_2 = 0;
    for (int j = 0; j < m; j++) {
      if ((j & 1) && vec[i][j] != b) tmp_2++;
      if (!(j & 1) && vec[i][j] != a) tmp_2++;
    }
    for (int j = 0; j < m; j++) {
      if (j & 1) res_vec_tmp1[i][j] = tmp_1 < tmp_2 ? a : b;
      if (!(j & 1)) res_vec_tmp1[i][j] = tmp_1 < tmp_2 ? b : a;
    }
    ans_r += min(tmp_1, tmp_2);
  }
  for (int i = 1; i < n; i += 2) {
    int tmp_1 = 0, tmp_2 = 0;
    for (int j = 0; j < m; j++) {
      if ((j & 1) && vec[i][j] != c) tmp_1++;
      if (!(j & 1) && vec[i][j] != d) tmp_1++;
    }
    for (int j = 0; j < m; j++) {
      if ((j & 1) && vec[i][j] != d) tmp_2++;
      if (!(j & 1) && vec[i][j] != c) tmp_2++;
    }
    for (int j = 0; j < m; j++) {
      if (j & 1) res_vec_tmp1[i][j] = tmp_1 < tmp_2 ? c : d;
      if (!(j & 1)) res_vec_tmp1[i][j] = tmp_1 < tmp_2 ? d : c;
    }
    ans_r += min(tmp_1, tmp_2);
  }
  if (ans > ans_r) ans = ans_r, res_vec = res_vec_tmp1;
  int ans_c = 0;
  for (int j = 0; j < m; j += 2) {
    int tmp_1 = 0, tmp_2 = 0;
    for (int i = 0; i < n; i++) {
      if ((i & 1) && vec[i][j] != a) tmp_1++;
      if (!(i & 1) && vec[i][j] != b) tmp_1++;
    }
    for (int i = 0; i < n; i++) {
      if ((i & 1) && vec[i][j] != b) tmp_2++;
      if (!(i & 1) && vec[i][j] != a) tmp_2++;
    }
    for (int i = 0; i < n; i++) {
      if (i & 1) res_vec_tmp2[i][j] = tmp_1 < tmp_2 ? a : b;
      if (!(i & 1)) res_vec_tmp2[i][j] = tmp_1 < tmp_2 ? b : a;
    }
    ans_c += min(tmp_1, tmp_2);
  }
  for (int j = 1; j < m; j += 2) {
    int tmp_1 = 0, tmp_2 = 0;
    for (int i = 0; i < n; i++) {
      if ((i & 1) && vec[i][j] != c) tmp_1++;
      if (!(i & 1) && vec[i][j] != d) tmp_1++;
    }
    for (int i = 0; i < n; i++) {
      if ((i & 1) && vec[i][j] != d) tmp_2++;
      if (!(i & 1) && vec[i][j] != c) tmp_2++;
    }
    for (int i = 0; i < n; i++) {
      if (i & 1) res_vec_tmp2[i][j] = tmp_1 < tmp_2 ? c : d;
      if (!(i & 1)) res_vec_tmp2[i][j] = tmp_1 < tmp_2 ? d : c;
    }
    ans_c += min(tmp_1, tmp_2);
  }
  if (ans > ans_c) ans = ans_c, res_vec = res_vec_tmp2;
  return;
}
int main() {
  while (cin >> n >> m) {
    vec.clear();
    res_vec.clear();
    res_vec_tmp1.clear();
    res_vec_tmp2.clear();
    for (int i = 0; i < n; i++) {
      string tmp;
      cin >> tmp;
      vec.push_back(tmp);
      res_vec_tmp1.push_back(tmp);
      res_vec_tmp2.push_back(tmp);
    }
    ans = 1000000001;
    for (int i = 0; i < 4; i++) {
      for (int j = i + 1; j < 4; j++) {
        for (int k = 0; k < 4; k++) {
          if (k == i || k == j) continue;
          for (int p = k + 1; p < 4; p++) {
            if (p == i || p == j) continue;
            cal(str[i], str[j], str[k], str[p]);
          }
        }
      }
    }
    for (int i = 0; i < n; i++) {
      cout << res_vec[i] << endl;
    }
  }
  return 0;
}
