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 N = 312345;
const int INF = int(1e9);
string s[N], ans[N], cur[N];
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int r, c;
  cin >> r >> c;
  for (int i = 0; i < r; i++) cin >> s[i];
  for (int i = 0; i < r; i++) cur[i].resize(c);
  string chars = "ACGT";
  int tim = INF;
  do {
    int tot = 0;
    for (int i = 0; i < r; i++) {
      int cnt0 = 0, cnt1 = 0;
      for (int j = 0; j < c; j++) {
        if (s[i][j] != chars[(i & 1) * 2 + (j & 1)]) cnt0++;
        if (s[i][j] != chars[(i & 1) * 2 + ((j ^ 1) & 1)]) cnt1++;
      }
      if (cnt0 < cnt1) {
        for (int j = 0; j < c; j++) cur[i][j] = chars[(i & 1) * 2 + (j & 1)];
        tot += cnt0;
      } else {
        for (int j = 0; j < c; j++)
          cur[i][j] = chars[(i & 1) * 2 + ((j ^ 1) & 1)];
        tot += cnt1;
      }
    }
    if (tot < tim) {
      for (int i = 0; i < r; i++) ans[i] = cur[i];
      tim = tot;
    }
    tot = 0;
    for (int j = 0; j < c; j++) {
      int cnt0 = 0, cnt1 = 0;
      for (int i = 0; i < r; i++) {
        if (s[i][j] != chars[(i & 1) * 2 + (j & 1)]) cnt0++;
        if (s[i][j] != chars[((i ^ 1) & 1) * 2 + (j & 1)]) cnt1++;
      }
      if (cnt0 < cnt1) {
        for (int i = 0; i < r; i++) cur[i][j] = chars[(i & 1) * 2 + (j & 1)];
        tot += cnt0;
      } else {
        for (int i = 0; i < r; i++)
          cur[i][j] = chars[((i ^ 1) & 1) * 2 + (j & 1)];
        tot += cnt1;
      }
    }
    if (tot < tim) {
      for (int i = 0; i < r; i++) ans[i] = cur[i];
      tim = tot;
    }
  } while (next_permutation((chars).begin(), (chars).end()));
  for (int i = 0; i < r; i++) cout << ans[i] << '\n';
  return 0;
}
