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>
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
using namespace std;
mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
const long long M = 1e9 + 7;
const long long N = 5002;
int fun(vector<string> &s) {
  int res = M;
  vector<string> tmp = s;
  int n = s.size(), m = s[0].size();
  for (int F = 0; F < 3; F++)
    for (int S = F + 1; S < 4; S++) {
      vector<char> v[2];
      v[0].push_back(F + '0');
      v[0].push_back(S + '0');
      for (int k = 0; k < 4; k++)
        if (k != F && k != S) v[1].push_back(k + '0');
      int sum = 0;
      for (int i = 0; i < n; i++) {
        int cur[2] = {};
        for (int j = 0; j < m; j++) cur[0] += v[i % 2][j % 2] != s[i][j];
        for (int j = 0; j < m; j++) cur[1] += v[i % 2][1 - j % 2] != s[i][j];
        sum += min(cur[0], cur[1]);
      }
      if (res > sum) {
        res = sum;
        for (int i = 0; i < n; i++) {
          int cur[2] = {};
          for (int j = 0; j < m; j++) cur[0] += v[i % 2][j % 2] != s[i][j];
          for (int j = 0; j < m; j++) cur[1] += v[i % 2][1 - j % 2] != s[i][j];
          if (cur[0] < cur[1])
            for (int j = 0; j < m; j++) tmp[i][j] = v[i % 2][j % 2];
          else
            for (int j = 0; j < m; j++) tmp[i][j] = v[i % 2][1 - j % 2];
        }
      }
    }
  s = tmp;
  return res;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  map<char, char> mp;
  vector<char> v = {'A', 'C', 'G', 'T'};
  vector<char> v1 = {'0', '1', '2', '3'};
  for (int i = 0; i < 4; i++) mp[v[i]] = v1[i], mp[v1[i]] = v[i];
  int n, m;
  cin >> n >> m;
  vector<string> s(n), t(m), res;
  for (int i = 0; i < n; i++) cin >> s[i];
  for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++) s[i][j] = mp[s[i][j]];
  for (int i = 0; i < m; i++) {
    t[i] = "";
    for (int j = 0; j < n; j++) t[i] += s[j][i];
  }
  bool ok = true;
  if (fun(s) < fun(t))
    res = s;
  else
    res = t, ok = false;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      if (ok)
        cout << mp[res[i][j]];
      else
        cout << mp[res[j][i]];
    }
    cout << endl;
  }
}
