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;
template <typename T>
void read_to_vector(size_t N, std::vector<T> &v) {
  for (size_t i = 0; i < N; i++) {
    T tmp;
    std::cin >> tmp;
    v.push_back(tmp);
  }
}
template <typename T>
void print_vector(const std::vector<T> &v) {
  for (auto it = v.begin(); it < v.end(); it++) {
    if (it != v.begin()) std::cout << " ";
    std::cout << (*it);
  }
}
long long n, m;
vector<string> t;
string xx[12] = {"AG", "AC", "AT", "GC", "GT", "CT",
                 "GA", "CA", "TA", "CG", "TG", "TC"};
vector<vector<long long> > row_xx(12, vector<long long>(1 << 20));
vector<vector<long long> > col_xx(12, vector<long long>(1 << 20));
vector<string> getbest_col(int x) {
  int xs[2] = {x, 5 - x};
  vector<string> res(n, string(m, '0'));
  for (int i = 0; i < m; i++) {
    string tothis;
    int xt = xs[i & 1];
    if (col_xx[xt][i] < col_xx[xt + 6][i]) {
      tothis = xx[xt];
    } else {
      tothis = xx[xt + 6];
    }
    for (int j = 0; j < n; j++) {
      res[j][i] = tothis[j & 1];
    }
  }
  return res;
}
vector<string> getbest_row(int x) {
  int xs[2] = {x, 5 - x};
  vector<string> res(n, string(m, '0'));
  for (int i = 0; i < n; i++) {
    string tothis;
    int xt = xs[i & 1];
    if (row_xx[xt][i] < row_xx[xt + 6][i]) {
      tothis = xx[xt];
    } else {
      tothis = xx[xt + 6];
    }
    for (int j = 0; j < m; j++) {
      res[i][j] = tothis[j & 1];
    }
  }
  return res;
}
long long eval(vector<string> &tt) {
  long long res = 0;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      res += (tt[i][j] != t[i][j]);
    }
  }
  return res;
}
void solve() {
  cin >> n >> m;
  read_to_vector(n, t);
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      for (int x = 0; x < 12; x++) {
        row_xx[x][i] += (t[i][j] != xx[x][j & 1]);
        col_xx[x][j] += (t[i][j] != xx[x][i & 1]);
      }
    }
  }
  vector<string> bestt = getbest_row(0);
  long long bestval = eval(bestt);
  for (int x = 0; x < 6; x++) {
    auto t0 = getbest_row(x);
    auto val0 = eval(t0);
    if (val0 < bestval) {
      bestt = t0;
      bestval = val0;
    }
  }
  for (int x = 0; x < 6; x++) {
    auto t0 = getbest_col(x);
    auto val0 = eval(t0);
    if (val0 < bestval) {
      bestt = t0;
      bestval = val0;
    }
  }
  for (auto s : bestt) {
    cout << s << "\n";
  }
  return;
}
void pre_compute() {}
int main() {
  std::cout << std::setprecision(15);
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);
  pre_compute();
  solve();
  return 0;
}
