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;
vector<vector<char>> best;
long long best_res = 1e18;
string s = "ACGT";
vector<char> row1, row2;
vector<vector<char>> current;
void solve(vector<vector<char>> a, bool rev) {
  long long n = a.size();
  long long m = a[0].size();
  current.resize(n, vector<char>(m));
  row1.resize(m);
  row2.resize(m);
  for (long long n1 = 0; n1 < 3; n1++) {
    for (long long n2 = n1 + 1; n2 < 4; n2++) {
      for (long long n3 = 0; n3 < 3; n3++) {
        if (n3 == n1 || n3 == n2) continue;
        for (long long n4 = n3 + 1; n4 < 4; n4++) {
          if (n4 == n1 || n4 == n2) continue;
          char c[2][2] = {{s[n1], s[n2]}, {s[n3], s[n4]}};
          long long res = 0;
          for (long long i = 0; i < n; i++) {
            long long res1 = 0, res2 = 0;
            for (long long j = 0; j < m; j++) {
              res1 += a[i][j] != c[i % 2][j % 2];
              row1[j] = c[i % 2][j % 2];
              res2 += a[i][j] != c[i % 2][(j + 1) % 2];
              row2[j] = c[i % 2][(j + 1) % 2];
            }
            if (res1 < res2) {
              res += res1;
              current[i] = row1;
            } else {
              res += res2;
              current[i] = row2;
            }
          }
          if (res < best_res) {
            best_res = res;
            for (long long i = 0; i < n; i++) {
              for (long long j = 0; j < m; j++) {
                if (!rev) {
                  best[i][j] = current[i][j];
                } else {
                  best[j][i] = current[i][j];
                }
              }
            }
          }
        }
      }
    }
  }
}
signed main() {
  cin.tie(0);
  cout.tie(0);
  ios_base ::sync_with_stdio(0);
  long long n, m;
  cin >> n >> m;
  best.resize(n, vector<char>(m));
  vector<vector<char>> a(n, vector<char>(m));
  for (long long i = 0; i < n; i++) {
    for (long long j = 0; j < m; j++) {
      cin >> a[i][j];
    }
  }
  solve(a, false);
  vector<vector<char>> b(m, vector<char>(n));
  for (long long i = 0; i < n; i++) {
    for (long long j = 0; j < m; j++) {
      b[j][i] = a[i][j];
    }
  }
  solve(b, true);
  for (long long i = 0; i < n; i++) {
    for (long long j = 0; j < m; j++) {
      cout << best[i][j];
    }
    cout << '\n';
  }
  return 0;
}
