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 out(T x) {
  cout << x << endl;
  exit(0);
}
const int maxn = 2005;
int n, m;
vector<string> g;
pair<int, string> solveRow(const string& row, char c1, char c2) {
  pair<int, string> s1, s2;
  for (size_t i = 0; i < row.size(); i++) {
    s1.second += c1;
    s1.first += s1.second[i] != row[i];
    s2.second += c2;
    s2.first += s2.second[i] != row[i];
    swap(c1, c2);
  }
  assert(s1.second.size() == row.size());
  assert(s2.second.size() == row.size());
  return min(s1, s2);
}
pair<int, vector<string>> solveRows(vector<string> g) {
  pair<int, vector<string>> best;
  vector<char> lets = {'A', 'C', 'G', 'T'};
  for (int i = 0; i < 4; i++) {
    for (int j = i + 1; j < 4; j++) {
      int a = i;
      int b = j;
      int c = 0;
      while (c == a || c == b) c++;
      int d = c + 1;
      while (d == a || d == b || d == c) d++;
      pair<int, vector<string>> cur;
      for (auto r : g) {
        auto res = solveRow(r, lets[a], lets[b]);
        cur.first += res.first;
        cur.second.push_back(res.second);
        swap(a, c);
        swap(b, d);
      }
      if (best.second.empty() || cur < best) {
        best = cur;
      }
    }
  }
  assert(!best.second.empty());
  return best;
}
vector<string> transpose(vector<string> g) {
  int n = g.size();
  int m = g[0].length();
  vector<string> h(m, string(n, 'x'));
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      h[j][i] = g[i][j];
    }
  }
  return h;
}
pair<int, vector<string>> solveCols(vector<string> g) {
  g = transpose(g);
  pair<int, vector<string>> res = solveRows(g);
  res.second = transpose(res.second);
  return res;
}
pair<int, vector<string>> solve(vector<string> g) {
  return min(solveRows(g), solveCols(g));
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> m;
  for (int i = 0; i < n; i++) {
    string buf;
    cin >> buf;
    g.push_back(buf);
  }
  pair<int, vector<string>> res = solve(g);
  cerr << res.first << endl;
  for (auto r : res.second) {
    cout << r << endl;
  }
  return 0;
}
