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;
vector<int> print(303456);
vector<int> auxprint;
vector<string> auxtxt;
int maxx[303456];
string txt[303456];
int n, m;
int maxresp;
bool tipox;
void clr() {
  for (int i = 0; i < 303456; ++i) {
    maxx[i] = -1;
  }
}
void calc(vector<string> &act) {
  clr();
  for (int x = 0; x < m; ++x) {
    for (int j = 0; j < 2; j++) {
      int c = 0;
      for (int y = 0; y < n; y++) {
        if (txt[y][x] == act[x % 2][(y + j) % 2]) c++;
      }
      if (c > maxx[x]) maxx[x] = c, print[x] = j;
    }
  }
  int tot = 0;
  for (int x = 0; x < m; ++x) tot += maxx[x];
  if (tot > maxresp) {
    tipox = 1;
    maxresp = tot;
    auxtxt = act;
    auxprint = print;
  }
  clr();
  for (int y = 0; y < n; y++) {
    for (int j = 0; j < 2; j++) {
      int c = 0;
      for (int x = 0; x < m; x++) {
        if (txt[y][x] == act[y % 2][(x + j) % 2]) {
          c++;
        }
      }
      if (c > maxx[y]) print[y] = j, maxx[y] = c;
    }
  }
  tot = 0;
  for (int y = 0; y < n; y++) tot += maxx[y];
  if (tot > maxresp) {
    tipox = 0;
    maxresp = tot;
    auxtxt = act;
    auxprint = print;
  }
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  maxresp = 0;
  cin >> n >> m;
  for (int i = 0; i < n; ++i) {
    cin >> txt[i];
  }
  string permutar = "ACGT";
  do {
    vector<string> auxp;
    auxp.push_back(permutar.substr(0, 2));
    auxp.push_back(permutar.substr(2));
    calc(auxp);
  } while (next_permutation(permutar.begin(), permutar.end()));
  if (tipox == 1) {
    for (int x = 0; x < m; ++x) {
      for (int y = 0; y < n; y++) {
        txt[y][x] = auxtxt[x % 2][(y + auxprint[x]) % 2];
      }
    }
  } else {
    for (int y = 0; y < n; y++) {
      for (int x = 0; x < m; x++) {
        txt[y][x] = auxtxt[y % 2][(x + auxprint[y]) % 2];
      }
    }
  }
  for (int i = 0; i < n; ++i) {
    cout << txt[i] << endl;
  }
}
