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 = 2e5 + 50;
const int M = 1e6;
const long long oo = 1e18;
const int mod = 1e9 + 7;
int main() {
  int n, m;
  cin >> n >> m;
  vector<string> s(n), ans;
  for (int i = 0; i < n; i++) cin >> s[i];
  string a = "AGCT";
  int mn = 1e9;
  do {
    vector<string> tmp = s;
    int cst = 0;
    for (int i = 0; i < n; i++) {
      int dif1 = 0, dif2 = 0;
      for (int j = 0; j < m; j++) {
        dif1 += (tmp[i][j] != a[2 * (i & 1) + (j & 1)]);
        dif2 += (tmp[i][j] != a[2 * (i & 1) + ((j ^ 1) & 1)]);
      }
      cst += min(dif1, dif2);
      for (int j = 0; j < m; j++) {
        if (dif1 < dif2)
          tmp[i][j] = a[2 * (i & 1) + (j & 1)];
        else
          tmp[i][j] = a[2 * (i & 1) + ((j ^ 1) & 1)];
      }
    }
    if (cst < mn) {
      mn = cst;
      ans = tmp;
    }
    tmp = s;
    cst = 0;
    for (int j = 0; j < m; j++) {
      int dif1 = 0, dif2 = 0;
      for (int i = 0; i < n; i++) {
        dif1 += (tmp[i][j] != a[2 * (i & 1) + (j & 1)]);
        dif2 += (tmp[i][j] != a[2 * ((i ^ 1) & 1) + (j & 1)]);
      }
      cst += min(dif1, dif2);
      for (int i = 0; i < n; i++) {
        if (dif1 < dif2)
          tmp[i][j] = a[2 * (i & 1) + (j & 1)];
        else
          tmp[i][j] = a[2 * ((i ^ 1) & 1) + (j & 1)];
      }
    }
    if (cst < mn) {
      mn = cst;
      ans = tmp;
    }
  } while (next_permutation(a.begin(), a.end()));
  for (int i = 0; i < n; i++) {
    cout << ans[i] << endl;
  }
}
