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;
int R, C, res = INT_MAX;
bool swapped, c_swapped;
vector<vector<char>> arr, ans;
vector<char> v = {'A', 'C', 'G', 'T'};
inline void rotate(vector<vector<char>> &arr) {
  vector<vector<char>> nxt(C, vector<char>(R));
  for (int i = 0; i < C; i++)
    for (int k = 0; k < R; k++) nxt[i][k] = arr[k][C - i - 1];
  swap(arr, nxt);
}
inline vector<vector<char>> make(vector<char> t[2]) {
  vector<vector<char>> ans(R, vector<char>(C));
  for (int i = 0; i < R; i++) {
    int min_cost = INT_MAX, a = 0;
    for (int k = 0; k < 2; k++) {
      int cost = 0;
      for (int a = 0; a < C; a++) cost += arr[i][a] != t[i % 2][a % 2];
      if (cost < min_cost) {
        min_cost = cost;
        a = k;
      }
      swap(t[i % 2][0], t[i % 2][1]);
    }
    if (a) swap(t[i % 2][0], t[i % 2][1]);
    for (int k = 0; k < C; k++) ans[i][k] = t[i % 2][k % 2];
    if (a) swap(t[i % 2][0], t[i % 2][1]);
  }
  return ans;
}
void solve() {
  sort(v.begin(), v.end());
  do {
    vector<char> t[2];
    t[0] = {v[0], v[1]};
    t[1] = {v[2], v[3]};
    int sum = 0;
    for (int i = 0; i < R; i++) {
      int min_cost = INT_MAX;
      for (int k = 0; k < 2; k++) {
        int cost = 0;
        for (int a = 0; a < C; a++) cost += arr[i][a] != t[i % 2][a % 2];
        min_cost = min(min_cost, cost);
        swap(t[i % 2][0], t[i % 2][1]);
      }
      sum += min_cost;
    }
    if (sum < res) {
      if (c_swapped) swapped = true;
      res = sum;
      ans = make(t);
    }
  } while (next_permutation(v.begin(), v.end()));
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> R >> C;
  arr.resize(R);
  for (int i = 0; i < R; i++) {
    arr[i].resize(C);
    for (int k = 0; k < C; k++) cin >> arr[i][k];
  }
  solve();
  rotate(arr);
  swap(R, C);
  c_swapped = true;
  solve();
  if (swapped) {
    rotate(ans);
    swap(R, C);
    rotate(ans);
    swap(R, C);
    rotate(ans);
  }
  swap(R, C);
  for (int i = 0; i < R; i++) {
    for (int k = 0; k < C; k++) cout << ans[i][k];
    cout << '\n';
  }
}
