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 <class T>
void splitstr(const string &s, vector<T> &out) {
  istringstream in(s);
  out.clear();
  copy(istream_iterator<T>(in), istream_iterator<T>(), back_inserter(out));
}
template <class T>
T gcd(T a, T b) {
  return b ? gcd(b, a % b) : a;
}
static void redirect(int argc, const char **argv) {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  if (argc > 1) {
    static filebuf f;
    f.open(argv[1], ios::in);
    cin.rdbuf(&f);
    if (!cin) {
      cerr << "Failed to open '" << argv[1] << "'" << endl;
      exit(1);
    }
  }
  if (argc > 2) {
    static filebuf f;
    f.open(argv[2], ios::out | ios::trunc);
    cout.rdbuf(&f);
    if (!cout) {
      cerr << "Failed to open '" << argv[2] << "'" << endl;
    }
  }
}
static char chs[4] = {'A', 'C', 'G', 'T'};
static vector<string> transpose(const vector<string> &grid) {
  int R = ((long long)(grid).size());
  int C = ((long long)(grid[0]).size());
  vector<string> out(C, string(R, '?'));
  for (int i = 0; i < R; i++)
    for (int j = 0; j < C; j++) out[j][i] = grid[i][j];
  return out;
}
static int delta(const string &row1, const string &row2) {
  int ans = 0;
  for (int i = 0; i < ((long long)(row1).size()); i++)
    ans += row1[i] != row2[i];
  return ans;
}
static int delta(const vector<string> &grid1, const vector<string> &grid2) {
  int ans = 0;
  for (int i = 0; i < ((long long)(grid1).size()); i++)
    ans += delta(grid1[i], grid2[i]);
  return ans;
}
static pair<int, vector<string> > solve(const vector<string> &grid) {
  int R = ((long long)(grid).size());
  int C = ((long long)(grid[0]).size());
  pair<int, vector<string> > ans;
  ans.first = INT_MAX;
  for (int i = 0; i < 4; i++)
    for (int j = i + 1; j < 4; j++) {
      char ch[4];
      ch[0] = chs[i];
      ch[1] = chs[j];
      int k = 0;
      while (k == i || k == j) k++;
      ch[2] = chs[k++];
      while (k == i || k == j) k++;
      ch[3] = chs[k];
      vector<string> cand(R);
      for (int r = 0; r < R; r++) {
        int f = (r & 1) ? 2 : 0;
        string row[2];
        for (int c = 0; c < C; c++) {
          row[0] += ch[f + c % 2];
          row[1] += ch[f + (c + 1) % 2];
        }
        if (delta(grid[r], row[1]) < delta(grid[r], row[0]))
          cand[r] = move(row[1]);
        else
          cand[r] = move(row[0]);
      }
      int score = delta(grid, cand);
      if (score < ans.first) {
        ans.first = score;
        ans.second = cand;
      }
    }
  return ans;
}
int main(int argc, const char **argv) {
  redirect(argc, argv);
  int R, C;
  cin >> R >> C;
  vector<string> grid(R);
  for (int i = 0; i < R; i++) cin >> grid[i];
  pair<int, vector<string> > ans = solve(grid);
  grid = transpose(grid);
  pair<int, vector<string> > ans2 = solve(grid);
  if (ans2.first < ans.first) {
    ans.first = ans2.first;
    ans.second = transpose(ans2.second);
  }
  for (int i = 0; i < R; i++) cout << ans.second[i] << '\n';
  return 0;
}
