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;
using ld = long double;
using ll = long long;
using vi = vector<int>;
using pii = pair<int, int>;
vector<vector<char> > mapa;
vector<vector<char> > sol_mapa;
vector<vector<char> > aux_mapa;
vector<vector<char> > tmp_mapa;
vector<char> arr;
const char letras[4] = {'A', 'C', 'G', 'T'};
void init(int n, int m) {
  mapa.resize(n + 2, vector<char>(m + 2));
  sol_mapa.resize(n + 2, vector<char>(m + 2));
  aux_mapa.resize(n + 2, vector<char>(m + 2));
  tmp_mapa.resize(n + 2, vector<char>(m + 2));
}
int calcula(int n, int a, int b) {
  int v1 = 0, v2 = 0;
  for (int i = 1; i <= n; i++) {
    if (i & 1) {
      if (arr[i] != letras[a]) v1++;
      if (arr[i] != letras[b]) v2++;
    } else {
      if (arr[i] != letras[b]) v1++;
      if (arr[i] != letras[a]) v2++;
    }
  }
  if (v2 < v1) swap(a, b);
  for (int i = 1; i <= n; i++) {
    if (i & 1)
      arr[i] = letras[a];
    else
      arr[i] = letras[b];
  }
  return min(v1, v2);
}
int resuelve_filas(int n, int m, int a, int b, int c, int d) {
  int val = 0;
  arr.resize(m + 2);
  for (int i = 1; i <= n; i += 2) {
    for (int j = 1; j <= m; j++) arr[j] = mapa[i][j];
    val += calcula(m, a, b);
    for (int j = 1; j <= m; j++) aux_mapa[i][j] = arr[j];
  }
  for (int i = 2; i <= n; i += 2) {
    for (int j = 1; j <= m; j++) arr[j] = mapa[i][j];
    val += calcula(m, c, d);
    for (int j = 1; j <= m; j++) aux_mapa[i][j] = arr[j];
  }
  return val;
}
int resuelve_columnas(int n, int m, int a, int b, int c, int d) {
  int val = 0;
  arr.resize(n + 2);
  for (int j = 1; j <= m; j += 2) {
    for (int i = 1; i <= n; i++) arr[i] = mapa[i][j];
    val += calcula(n, a, b);
    for (int i = 1; i <= n; i++) tmp_mapa[i][j] = arr[i];
  }
  for (int j = 2; j <= m; j += 2) {
    for (int i = 1; i <= n; i++) arr[i] = mapa[i][j];
    val += calcula(n, c, d);
    for (int i = 1; i <= n; i++) tmp_mapa[i][j] = arr[i];
  }
  return val;
}
int resuelve(int n, int m, int a, int b, int c, int d) {
  int v1 = resuelve_filas(n, m, a, b, c, d);
  int v2 = resuelve_columnas(n, m, a, b, c, d);
  if (v2 < v1) swap(tmp_mapa, aux_mapa);
  return min(v1, v2);
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int n, m;
  cin >> n >> m;
  init(n, m);
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      cin >> mapa[i][j];
    }
  }
  int res = n * m + 1;
  vi acomodo(4);
  iota(acomodo.begin(), acomodo.end(), 0);
  do {
    int a = acomodo[0];
    int b = acomodo[1];
    int c = acomodo[2];
    int d = acomodo[3];
    int aux = resuelve(n, m, a, b, c, d);
    if (aux < res) {
      res = aux;
      swap(aux_mapa, sol_mapa);
    }
  } while (next_permutation(acomodo.begin(), acomodo.end()));
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      cout << sol_mapa[i][j];
    }
    cout << '\n';
  }
  return 0;
}
