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;
FILE* in = stdin;
FILE* out = stdout;
int n, m;
vector<string> board;
int main(void) {
  fscanf(in, "%d %d", &n, &m);
  for (int row = 0; row < n; row++) {
    static char buff[300003];
    fscanf(in, "%s", buff);
    board.push_back(buff);
  }
  int best = n * m + 1;
  vector<string> ans;
  vector<string> cand = board;
  string str = "ACGT";
  do {
    int curH = 0;
    for (int row = 0; row < n; row++) {
      int diff1 = 0, xr1 = 0;
      for (int col = 0; col < m; col++) {
        cand[row][col] = str[(row % 2) * 2 + ((col % 2) ^ xr1)];
        if (cand[row][col] != board[row][col]) diff1++;
      }
      int diff2 = 0, xr2 = 1;
      for (int col = 0; col < m; col++) {
        cand[row][col] = str[(row % 2) * 2 + ((col % 2) ^ xr2)];
        if (cand[row][col] != board[row][col]) diff2++;
      }
      if (diff1 < diff2) {
        for (int col = 0; col < m; col++)
          cand[row][col] = str[(row % 2) * 2 + ((col % 2) ^ xr1)];
      }
      curH += min(diff1, diff2);
    }
    if (best > curH) {
      best = curH;
      ans = cand;
    }
    int curV = 0;
    for (int col = 0; col < m; col++) {
      int diff1 = 0, xr1 = 0;
      for (int row = 0; row < n; row++) {
        cand[row][col] = str[(col % 2) * 2 + ((row % 2) ^ xr1)];
        if (cand[row][col] != board[row][col]) diff1++;
      }
      int diff2 = 0, xr2 = 1;
      for (int row = 0; row < n; row++) {
        cand[row][col] = str[(col % 2) * 2 + ((row % 2) ^ xr2)];
        if (cand[row][col] != board[row][col]) diff2++;
      }
      if (diff1 < diff2) {
        for (int row = 0; row < n; row++)
          cand[row][col] = str[(col % 2) * 2 + ((row % 2) ^ xr1)];
      }
      curV += min(diff1, diff2);
    }
    if (best > curV) {
      best = curV;
      ans = cand;
    }
  } while (next_permutation(str.begin(), str.end()));
  for (int row = 0; row < n; row++) fprintf(out, "%s\n", ans[row].c_str());
  return 0;
}
