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;
using ll = int64_t;
const ll INF = 5e15;
int main() {
  vector<char> chars = {'A', 'G', 'C', 'T'};
  ll N, M;
  cin >> N >> M;
  vector<string> SV(N);
  for (auto &s : SV) cin >> s;
  vector<vector<ll>> costN(N, vector<ll>(4 * 4));
  vector<vector<ll>> costM(M, vector<ll>(4 * 4));
  for (ll F = 0; F < 4; F++) {
    for (ll S = 0; S < 4; S++) {
      for (ll row = 0; row < N; row++) {
        for (ll i = 0; i < M; i++) {
          char c = chars[(i % 2 == 0 ? F : S)];
          costN[row][4 * F + S] += (SV[row][i] != c);
        }
      }
      for (ll col = 0; col < M; col++) {
        for (ll i = 0; i < N; i++) {
          char c = chars[(i % 2 == 0 ? F : S)];
          costM[col][4 * F + S] += (SV[i][col] != c);
        }
      }
    }
  }
  ll ans = INF;
  vector<ll> print;
  bool rowf;
  for (ll A = 0; A < 4; A++) {
    for (ll G = A + 1; G < 4; G++) {
      vector<ll> tmpv;
      for (ll i = 0; i < 4; i++)
        if (i != A && i != G) tmpv.push_back(i);
      ll C = tmpv[0], T = tmpv[1];
      ll cn = 0, cc = 0;
      vector<ll> cnv(N), ccv(M);
      for (ll row = 0; row < N; row++) {
        ll idx =
            row % 2 == 0
                ? (costN[row][4 * A + G] < costN[row][4 * G + A] ? 4 * A + G
                                                                 : 4 * G + A)
                : (costN[row][4 * C + T] < costN[row][4 * T + C] ? 4 * C + T
                                                                 : 4 * T + C);
        cn += costN[row][idx];
        cnv[row] = idx;
      }
      for (ll col = 0; col < M; col++) {
        ll idx =
            col % 2 == 0
                ? (costM[col][4 * A + G] < costM[col][4 * G + A] ? 4 * A + G
                                                                 : 4 * G + A)
                : (costM[col][4 * C + T] < costM[col][4 * T + C] ? 4 * C + T
                                                                 : 4 * T + C);
        cc += costM[col][idx];
        ccv[col] = idx;
      }
      if (ans > cn) {
        ans = cn;
        print = cnv;
        rowf = 1;
      }
      if (ans > cc) {
        ans = cc;
        print = ccv;
        rowf = 0;
      }
    }
  }
  for (ll i = 0; i < N; i++) {
    for (ll j = 0; j < M; j++) {
      ll mark = print[rowf ? i : j];
      char cf = chars[mark / 4];
      char cs = chars[mark % 4];
      char cp = rowf ? (j % 2 == 0 ? cf : cs) : (i % 2 == 0 ? cf : cs);
      printf("%c", cp);
    }
    printf("\n");
  }
  return 0;
}
