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;
string aux[300000], sol[300000];
long funcion(char x, char y, char w, char z, string pal[], long mayor, long n,
             long m) {
  pair<long, long> xx, yy, ww, zz;
  long cont = 0;
  for (long i = 0; i < n; i++) {
    xx.first = 0;
    yy.first = 0;
    ww.first = 0;
    zz.first = 0;
    xx.second = 0;
    yy.second = 0;
    ww.second = 0;
    zz.second = 0;
    aux[i].clear();
    for (long j = 0; j < m; j++) {
      if (i % 2 == 0) {
        if (pal[i][j] == x && j % 2 == 0) xx.first++;
        if (pal[i][j] == y && j % 2 == 0) yy.first++;
        if (pal[i][j] == x && j % 2 == 1) xx.second++;
        if (pal[i][j] == y && j % 2 == 1) yy.second++;
      }
      if (i % 2 == 1) {
        if (pal[i][j] == w && j % 2 == 0) ww.first++;
        if (pal[i][j] == z && j % 2 == 0) zz.first++;
        if (pal[i][j] == w && j % 2 == 1) ww.second++;
        if (pal[i][j] == z && j % 2 == 1) zz.second++;
      }
    }
    if (i % 2 == 0) {
      if (xx.first + yy.second > xx.second + yy.first) {
        for (long j = 0; j < m; j++) {
          if (j % 2 == 0) aux[i].push_back(x);
          if (j % 2 == 1) aux[i].push_back(y);
        }
        cont += xx.first + yy.second;
      } else {
        for (long j = 0; j < m; j++) {
          if (j % 2 == 0) aux[i].push_back(y);
          if (j % 2 == 1) aux[i].push_back(x);
        }
        cont += yy.first + xx.second;
      }
    }
    if (i % 2 == 1) {
      if (ww.first + zz.second > ww.second + zz.first) {
        for (long j = 0; j < m; j++) {
          if (j % 2 == 0) aux[i].push_back(w);
          if (j % 2 == 1) aux[i].push_back(z);
        }
        cont += ww.first + zz.second;
      } else {
        for (long j = 0; j < m; j++) {
          if (j % 2 == 0) aux[i].push_back(z);
          if (j % 2 == 1) aux[i].push_back(w);
        }
        cont += zz.first + ww.second;
      }
    }
  }
  if (cont > mayor) {
    for (long i = 0; i < n; i++) {
      sol[i].clear();
      for (long j = 0; j < m; j++) {
        sol[i].push_back(aux[i][j]);
      }
    }
    mayor = cont;
  }
  return mayor;
}
long funcion2(char x, char y, char w, char z, string pal[], long mayor, long n,
              long m) {
  pair<long, long> xx, yy, ww, zz;
  long cont = 0;
  for (long j = 0; j < n; j++) {
    aux[j].clear();
  }
  for (long i = 0; i < m; i++) {
    xx.first = 0;
    yy.first = 0;
    ww.first = 0;
    zz.first = 0;
    xx.second = 0;
    yy.second = 0;
    ww.second = 0;
    zz.second = 0;
    for (long j = 0; j < n; j++) {
      if (i % 2 == 0) {
        if (pal[j][i] == x && j % 2 == 0) xx.first++;
        if (pal[j][i] == y && j % 2 == 0) yy.first++;
        if (pal[j][i] == x && j % 2 == 1) xx.second++;
        if (pal[j][i] == y && j % 2 == 1) yy.second++;
      }
      if (i % 2 == 1) {
        if (pal[j][i] == w && j % 2 == 0) ww.first++;
        if (pal[j][i] == z && j % 2 == 0) zz.first++;
        if (pal[j][i] == w && j % 2 == 1) ww.second++;
        if (pal[j][i] == z && j % 2 == 1) zz.second++;
      }
    }
    if (i % 2 == 0) {
      if (xx.first + yy.second > xx.second + yy.first) {
        for (long j = 0; j < n; j++) {
          if (j % 2 == 0) aux[j].push_back(x);
          if (j % 2 == 1) aux[j].push_back(y);
        }
        cont += xx.first + yy.second;
      } else {
        for (long j = 0; j < n; j++) {
          if (j % 2 == 0) aux[j].push_back(y);
          if (j % 2 == 1) aux[j].push_back(x);
        }
        cont += yy.first + xx.second;
      }
    }
    if (i % 2 == 1) {
      if (ww.first + zz.second > ww.second + zz.first) {
        for (long j = 0; j < n; j++) {
          if (j % 2 == 0) aux[j].push_back(w);
          if (j % 2 == 1) aux[j].push_back(z);
        }
        cont += ww.first + zz.second;
      } else {
        for (long j = 0; j < n; j++) {
          if (j % 2 == 0) aux[j].push_back(z);
          if (j % 2 == 1) aux[j].push_back(w);
        }
        cont += zz.first + ww.second;
      }
    }
  }
  if (cont > mayor) {
    for (long i = 0; i < n; i++) {
      sol[i].clear();
      for (long j = 0; j < m; j++) {
        sol[i].push_back(aux[i][j]);
      }
    }
    mayor = cont;
  }
  return mayor;
}
int main() {
  long n, m;
  cin >> n >> m;
  string pal[300000];
  for (long i = 0; i < n; i++) {
    cin >> pal[i];
  }
  long mayor = 0;
  mayor = funcion('A', 'C', 'G', 'T', pal, mayor, n, m);
  mayor = funcion('G', 'T', 'A', 'C', pal, mayor, n, m);
  mayor = funcion('A', 'G', 'C', 'T', pal, mayor, n, m);
  mayor = funcion('A', 'T', 'G', 'C', pal, mayor, n, m);
  mayor = funcion('C', 'T', 'A', 'G', pal, mayor, n, m);
  mayor = funcion('G', 'C', 'A', 'T', pal, mayor, n, m);
  mayor = funcion2('A', 'C', 'G', 'T', pal, mayor, n, m);
  mayor = funcion2('G', 'T', 'A', 'C', pal, mayor, n, m);
  mayor = funcion2('A', 'G', 'C', 'T', pal, mayor, n, m);
  mayor = funcion2('A', 'T', 'G', 'C', pal, mayor, n, m);
  mayor = funcion2('C', 'T', 'A', 'G', pal, mayor, n, m);
  mayor = funcion2('G', 'C', 'A', 'T', pal, mayor, n, m);
  for (long i = 0; i < n; i++) {
    cout << sol[i] << endl;
  }
  return 0;
}
