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;
void out() {
  cout.flush();
  int n;
  cin >> n;
  exit(0);
}
void WA() {
  cout << "No\n";
  out();
}
vector<string> s;
vector<string> invert(const vector<string> &s) {
  int n = s.size();
  int m = s[0].length();
  vector<string> a(m, "");
  for (int j = 0; j < m; ++j)
    for (int i = 0; i < n; ++i) a[j].push_back(s[i][j]);
  return a;
}
int findDist(const string &s, const string &t) {
  int ans = 0;
  for (int i = 0; i < (int)s.size(); ++i) ans += (s[i] != t[i]);
  return ans;
}
string gen(int n, char c1, char c2) {
  string s = "";
  for (int i = 0; i < n; ++i) {
    s.push_back(c1);
    swap(c1, c2);
  }
  return s;
}
int ans;
pair<int, vector<string> > findHor() {
  char CS[4] = {'A', 'C', 'G', 'T'};
  int n = s.size();
  int m = s[0].size();
  pair<int, vector<string> > ans(1000000, vector<string>());
  do {
    string AC = gen(m, CS[0], CS[1]);
    string CA = gen(m, CS[1], CS[0]);
    string GT = gen(m, CS[2], CS[3]);
    string TG = gen(m, CS[3], CS[2]);
    vector<string> ss;
    int sum = 0;
    for (int i = 0; i < n; ++i) {
      int d1 = findDist(s[i], AC);
      int d2 = findDist(s[i], CA);
      if (d1 < d2) {
        sum += d1;
        ss.push_back(AC);
      } else {
        sum += d2;
        ss.push_back(CA);
      }
      AC.swap(GT);
      CA.swap(TG);
    }
    if (ans.first > sum) ans = make_pair(sum, ss);
  } while (next_permutation(CS, CS + 4));
  return ans;
}
pair<int, vector<string> > findVert() {
  s = invert(s);
  pair<int, vector<string> > ans = findHor();
  s = invert(s);
  ans.second = invert(ans.second);
  return ans;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int n, m;
  cin >> n >> m;
  s.resize(n);
  for (int i = 0; i < n; ++i) cin >> s[i];
  pair<int, vector<string> > ans = min(findHor(), findVert());
  for (int i = 0; i < n; ++i) cout << ans.second[i] << "\n";
  out();
  return 0;
}
