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 vx[300000][4][4] = {}, vy[300000][4][4] = {};
int Index(char c) {
  if (c == 'A') return 0;
  if (c == 'C') return 1;
  if (c == 'G') return 2;
  return 3;
}
char NumToChar(int ind) {
  if (ind == 0) return 'A';
  if (ind == 1) return 'C';
  if (ind == 2) return 'G';
  return 'T';
}
vector<vector<char>> megT;
void Kiir(int n, int j, int a, int b) {
  for (int i = 0; i < n; i++) {
    if (i % 2 == 0)
      megT[j][i] = NumToChar(a);
    else
      megT[j][i] = NumToChar(b);
  }
  return;
}
void Kiir2(int n, int j, int a, int b) {
  for (int i = 0; i < n; i++) {
    if (i % 2 == 0)
      megT[i][j] = NumToChar(a);
    else
      megT[i][j] = NumToChar(b);
  }
  return;
}
int main() {
  cin.sync_with_stdio(false);
  cin.tie(0);
  int n, m;
  cin >> n >> m;
  vector<vector<char>> table(n, vector<char>(m));
  megT.resize(n, vector<char>(m));
  vector<int> v = {0, 1, 2, 3};
  for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++) cin >> table[i][j];
  for (int x = 0; x < 4; x++) {
    for (int y = 0; y < 4; y++) {
      if (x == y) continue;
      for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
          if (j % 2 == 0 && Index(table[i][j]) == x)
            vx[i][x][y]++;
          else if (j % 2 == 1 && Index(table[i][j]) == y)
            vx[i][x][y]++;
        }
      }
    }
  }
  for (int x = 0; x < 4; x++) {
    for (int y = 0; y < 4; y++) {
      if (x == y) continue;
      for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
          if (j % 2 == 0 && Index(table[j][i]) == x)
            vy[i][x][y]++;
          else if (j % 2 == 1 && Index(table[j][i]) == y)
            vy[i][x][y]++;
        }
      }
    }
  }
  vector<int> megVX, megVY;
  int megX = -1, megY = -1;
  do {
    int akt = 0;
    for (int i = 0; i < n; i++) {
      if (i % 2 == 0)
        akt += max(vx[i][v[0]][v[1]], vx[i][v[1]][v[0]]);
      else
        akt += max(vx[i][v[2]][v[3]], vx[i][v[3]][v[2]]);
    }
    if (akt > megX) {
      megVX = v;
      megX = akt;
    }
    akt = 0;
    for (int i = 0; i < m; i++) {
      if (i % 2 == 0)
        akt += max(vy[i][v[0]][v[1]], vy[i][v[1]][v[0]]);
      else
        akt += max(vy[i][v[2]][v[3]], vy[i][v[3]][v[2]]);
    }
    if (akt > megY) {
      megVY = v;
      megY = akt;
    }
  } while (next_permutation(v.begin(), v.end()));
  if (megX >= megY) {
    v = megVX;
    for (int i = 0; i < n; i++) {
      if (i % 2 == 0) {
        if (vx[i][v[0]][v[1]] > vx[i][v[1]][v[0]])
          Kiir(m, i, v[0], v[1]);
        else
          Kiir(m, i, v[1], v[0]);
      } else {
        if (vx[i][v[2]][v[3]] > vx[i][v[3]][v[2]])
          Kiir(m, i, v[2], v[3]);
        else
          Kiir(m, i, v[3], v[2]);
      }
    }
  } else {
    v = megVY;
    for (int i = 0; i < m; i++) {
      if (i % 2 == 0) {
        if (vy[i][v[0]][v[1]] > vy[i][v[1]][v[0]])
          Kiir2(n, i, v[0], v[1]);
        else
          Kiir2(n, i, v[1], v[0]);
      } else {
        if (vy[i][v[2]][v[3]] > vy[i][v[3]][v[2]])
          Kiir2(n, i, v[2], v[3]);
        else
          Kiir2(n, i, v[3], v[2]);
      }
    }
  }
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) cout << megT[i][j];
    cout << "\n";
  }
  return 0;
}
