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>
int N, M, Flag, Min;
std::string S[300005], B[300005], Ans[300005];
std::string Sol;
std::bitset<300005> Bits;
void Solve(const std::string& Pattern, bool Part) {
  std::bitset<300005> Solution;
  int Count = 0, c1, c2;
  for (int i = 0, j, c1, c2; i < N; ++i) {
    c1 = c2 = 0;
    for (j = 0; j < M; ++j)
      c1 += (S[i][j] != Pattern[((i & 1) * 2 + (j & 1))]),
          c2 += (S[i][j] != Pattern[((i & 1) * 2 + (j & 1) ^ 1)]);
    if (c2 < c1)
      Solution[i] = 1, Count += c2;
    else
      Count += c1;
  }
  if (Count < Min) {
    Min = Count;
    Sol = Pattern;
    Bits = Solution;
    Flag = Part;
  }
}
void SolvePart(bool Part) {
  std::string Pattern = "ACGT";
  do {
    Solve(Pattern, Part);
  } while (std::next_permutation(Pattern.begin(), Pattern.end()));
}
void RotateMatrix(std::string (&A)[300005]) {
  for (int i = 0; i < M; ++i) B[i].clear();
  for (int i = 0, j; i < M; ++i)
    for (j = 0; j < N; ++j) B[i] += A[j][i];
  std::swap(N, M);
  for (int i = 0; i < N; ++i) A[i] = B[i];
}
void Citire() {
  std::cin >> N >> M;
  for (int i = 0; i < N; ++i) std::cin >> S[i];
}
void Rezolvare() {
  Min = 300005 + 10;
  SolvePart(false);
  RotateMatrix(S);
  SolvePart(true);
  if (!Flag) std::swap(N, M);
  for (int i = 0, j; i < N; ++i)
    for (j = 0; j < M; ++j) Ans[i] += Sol[(i & 1) * 2 + (j & 1) ^ Bits[i]];
  if (Flag) RotateMatrix(Ans);
  for (int i = 0; i < N; ++i, std::cout << '\n') std::cout << Ans[i];
}
int main() {
  Citire();
  Rezolvare();
  return 0;
}
