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>
bool uin(T &a, T b) {
  return a > b ? (a = b, true) : false;
}
template <class T>
bool uax(T &a, T b) {
  return a < b ? (a = b, true) : false;
}
const int maxn = 310000;
string f[maxn];
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.precision(10);
  cout << fixed;
  int n, m;
  cin >> n >> m;
  for (int i = 0; i < (int)(n); ++i) cin >> f[i];
  string chars = "ACGT";
  string bchars;
  bool frows;
  vector<int> to_flip;
  int bcost = 1e9;
  do {
    {
      vector<int> flip_rows(n);
      int cost = 0;
      for (int i = 0; i < (int)(n); ++i) {
        int dif0 = 0, dif1 = 0;
        for (int j = 0; j < (int)(m); ++j) {
          if (f[i][j] != chars[2 * (i & 1) + (j & 1)]) ++dif0;
          if (f[i][j] != chars[2 * (i & 1) + ((j ^ 1) & 1)]) ++dif1;
        }
        cost += min(dif0, dif1);
        flip_rows[i] = dif0 < dif1 ? 0 : 1;
      }
      if (uin(bcost, cost)) {
        bchars = chars;
        frows = 1;
        to_flip = flip_rows;
      }
    }
    {
      vector<int> flip_cols(m);
      int cost = 0;
      for (int j = 0; j < (int)(m); ++j) {
        int dif0 = 0, dif1 = 0;
        for (int i = 0; i < (int)(n); ++i) {
          if (f[i][j] != chars[2 * (i & 1) + (j & 1)]) ++dif0;
          if (f[i][j] != chars[2 * ((i ^ 1) & 1) + (j & 1)]) ++dif1;
        }
        cost += min(dif0, dif1);
        flip_cols[j] = dif0 < dif1 ? 0 : 1;
      }
      if (uin(bcost, cost)) {
        bchars = chars;
        frows = 0;
        to_flip = flip_cols;
      }
    }
  } while (next_permutation((chars).begin(), (chars).end()));
  if (frows) {
    for (int i = 0; i < (int)(n); ++i) {
      for (int j = 0; j < (int)(m); ++j)
        cout << bchars[2 * (i & 1) + ((j ^ to_flip[i]) & 1)];
      cout << '\n';
    }
  } else {
    for (int i = 0; i < (int)(n); ++i) {
      for (int j = 0; j < (int)(m); ++j)
        cout << bchars[2 * ((i ^ to_flip[j]) & 1) + (j & 1)];
      cout << '\n';
    }
  }
  return 0;
}
