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 dx[8] = {0, 0, -1, 1, 1, 1, -1, -1};
int dy[8] = {-1, 1, 0, 0, 1, -1, 1, -1};
const int SIZE = 100050;
int bitcount32(int dw32) {
  dw32 = ((dw32 & 0xAAAAAAAA) >> 1) + (dw32 & 0x55555555);
  dw32 = ((dw32 & 0xCCCCCCCC) >> 2) + (dw32 & 0x33333333);
  dw32 = ((dw32 & 0xF0F0F0F0) >> 4) + (dw32 & 0x0F0F0F0F);
  dw32 = ((dw32 & 0xFF00FF00) >> 8) + (dw32 & 0x00FF00FF);
  dw32 = ((dw32 & 0xFFFF0000) >> 16) + (dw32 & 0x0000FFFF);
  return dw32;
}
pair<int, string> mincos(string S, string T) {
  int a = 0;
  for (int i = 0; i < S.length(); i++) {
    if (S[i] != T[i % 2]) a++;
  }
  reverse(T.begin(), T.end());
  int b = 0;
  for (int i = 0; i < S.length(); i++) {
    if (S[i] != T[i % 2]) b++;
  }
  string U;
  if (a < b) {
    reverse(T.begin(), T.end());
  }
  for (int i = 0; i < S.length(); i++) U += T[i % 2];
  return make_pair(min(a, b), U);
}
int main() {
  int N, M;
  cin >> N >> M;
  vector<string> S;
  int msty = 0, mstt = 0;
  for (int i = 0; i < N; i++) {
    string T;
    cin >> T;
    S.push_back(T);
  }
  string T = "AGCT";
  int yoko = 0x3f3f3f3f, tate = 0x3f3f3f3f;
  for (int state = 0; state < (1 << 4); state++) {
    if (bitcount32(state) != 2) continue;
    int temp = 0;
    string U, V;
    for (int i = 0; i < 4; i++) {
      if (1 & (state >> i))
        U += T[i];
      else
        V += T[i];
    }
    for (int i = 0; i < N; i++) {
      pair<int, string> is;
      if (i % 2)
        is = mincos(S[i], U);
      else
        is = mincos(S[i], V);
      temp += is.first;
    }
    if (temp < yoko) {
      yoko = temp;
      msty = state;
    }
  }
  for (int state = 0; state < (1 << 4); state++) {
    if (bitcount32(state) != 2) continue;
    int temp = 0;
    string U, V;
    for (int i = 0; i < 4; i++) {
      if (1 & (state >> i))
        U += T[i];
      else
        V += T[i];
    }
    for (int i = 0; i < M; i++) {
      string W;
      for (int j = 0; j < N; j++) W += S[j][i];
      pair<int, string> is;
      if (i % 2)
        is = mincos(W, U);
      else
        is = mincos(W, V);
      temp += is.first;
    }
    if (temp < tate) {
      tate = temp;
      mstt = state;
    }
  }
  if (yoko < tate) {
    string U, V;
    for (int i = 0; i < 4; i++) {
      if (1 & (msty >> i))
        U += T[i];
      else
        V += T[i];
    }
    for (int i = 0; i < N; i++) {
      pair<int, string> is;
      if (i % 2)
        is = mincos(S[i], U);
      else
        is = mincos(S[i], V);
      cout << is.second << endl;
    }
  } else {
    vector<string> Y;
    string U, V;
    for (int i = 0; i < 4; i++) {
      if (1 & (mstt >> i))
        U += T[i];
      else
        V += T[i];
    }
    for (int i = 0; i < M; i++) {
      string W;
      for (int j = 0; j < N; j++) W += S[j][i];
      pair<int, string> is;
      if (i % 2)
        is = mincos(W, U);
      else
        is = mincos(W, V);
      Y.push_back(is.second);
    }
    for (int i = 0; i < N; i++) {
      for (int j = 0; j < M; j++) cout << Y[j][i];
      cout << endl;
    }
  }
  return 0;
}
