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 long long INF = 1e9 + 2;
const long long MOD = 998244353;
const long long MAXN = 1000006;
long long M, N;
vector<string> Board;
char Letras[] = "ACGT";
char Even[2];
char Odd[2];
vector<string> BoardTest;
vector<string> BoardAns;
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> N >> M;
  string s;
  for (int i = 0; i < int(N); i++) {
    cin >> s;
    Board.push_back(s);
    BoardTest.push_back(s);
    BoardAns.push_back(s);
  }
  long long ans = INF;
  for (int i = 0; i < int(4); i++)
    for (int j = i + 1; j < 4; j++) {
      Even[0] = Letras[i];
      Even[1] = Letras[j];
      int oddCtr = 0;
      for (int k = 0; k < int(4); k++)
        if (Letras[k] != Even[0] and Letras[k] != Even[1])
          Odd[oddCtr++] = Letras[k];
      long long actAns = 0;
      for (int f = 0; f < int(N); f++) {
        int bestOff = 0;
        int bestDiff = INF;
        if (f % 2) {
          for (int offset = 0; offset < int(2); offset++) {
            int diff = 0;
            for (int pos = 0; pos < int(M); pos++)
              if (Board[f][pos] != Even[(pos + offset) % 2]) diff++;
            if (diff < bestDiff) {
              bestOff = offset;
              bestDiff = diff;
            }
          }
          for (int pos = 0; pos < int(M); pos++)
            BoardTest[f][pos] = Even[(pos + bestOff) % 2];
        } else {
          for (int offset = 0; offset < int(2); offset++) {
            int diff = 0;
            for (int pos = 0; pos < int(M); pos++)
              if (Board[f][pos] != Odd[(pos + offset) % 2]) diff++;
            if (diff < bestDiff) {
              bestOff = offset;
              bestDiff = diff;
            }
          }
          for (int pos = 0; pos < int(M); pos++)
            BoardTest[f][pos] = Odd[(pos + bestOff) % 2];
        }
        actAns += bestDiff;
      }
      if (actAns < ans) {
        ans = actAns;
        BoardAns = BoardTest;
      }
      ans = min(actAns, ans);
      actAns = 0;
      for (int c = 0; c < int(M); c++) {
        int bestOff = 0;
        int bestDiff = INF;
        if (c % 2) {
          for (int offset = 0; offset < int(2); offset++) {
            int diff = 0;
            for (int pos = 0; pos < int(N); pos++)
              if (Board[pos][c] != Even[(pos + offset) % 2]) diff++;
            if (diff < bestDiff) {
              bestOff = offset;
              bestDiff = diff;
            }
          }
          for (int pos = 0; pos < int(N); pos++)
            BoardTest[pos][c] = Even[(pos + bestOff) % 2];
        } else {
          for (int offset = 0; offset < int(2); offset++) {
            int diff = 0;
            for (int pos = 0; pos < int(N); pos++)
              if (Board[pos][c] != Odd[(pos + offset) % 2]) diff++;
            if (diff < bestDiff) {
              bestOff = offset;
              bestDiff = diff;
            }
          }
          for (int pos = 0; pos < int(N); pos++)
            BoardTest[pos][c] = Odd[(pos + bestOff) % 2];
        }
        actAns += bestDiff;
      }
      if (actAns < ans) {
        ans = actAns;
        BoardAns = BoardTest;
      }
    }
  for (int i = 0; i < int(N); i++) cout << BoardAns[i] << '\n';
  return 0;
}
