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>
inline bool chkmin(T &a, const T &b) {
  return b < a ? a = b, 1 : 0;
}
template <typename T>
inline bool chkmax(T &a, const T &b) {
  return a < b ? a = b, 1 : 0;
}
const int oo = 0x3f3f3f3f;
inline int c2i(const char &c) {
  if (c == 'A') return 0;
  if (c == 'G') return 1;
  if (c == 'C') return 2;
  if (c == 'T') return 3;
  return -1;
}
inline char i2c(const int first) {
  if (first == 0) return 'A';
  if (first == 1) return 'G';
  if (first == 2) return 'C';
  if (first == 3) return 'T';
  return -1;
}
const int maxn = 300100;
int n, m;
vector<int> a[maxn + 5];
vector<int> ans[maxn + 5];
int ans_flip = -1;
int Max = -1;
inline void transpose(vector<int> *b) {
  vector<int> c[maxn + 5];
  for (int i = (0), i_end_ = (m); i < i_end_; ++i) c[i].resize(n);
  for (int i = (0), i_end_ = (n); i < i_end_; ++i)
    for (int j = (0), j_end_ = (m); j < j_end_; ++j) c[j][i] = b[i][j];
  for (int i = (0), i_end_ = (n); i < i_end_; ++i) b[i].clear();
  for (int i = (0), i_end_ = (m); i < i_end_; ++i) b[i] = c[i];
}
int main() {
  static char ss[maxn + 5];
  scanf("%d%d", &n, &m);
  for (int i = (0), i_end_ = (n); i < i_end_; ++i) {
    scanf("%s", ss);
    for (int j = (0), j_end_ = (m); j < j_end_; ++j) a[i].push_back(c2i(ss[j]));
  }
  Max = -1;
  for (int flip = (0), flip_end_ = (2); flip < flip_end_; ++flip) {
    static vector<int> tmp[maxn + 5];
    for (int i = (0), i_end_ = (n); i < i_end_; ++i) tmp[i].resize(m);
    for (int a00 = (0), a00_end_ = (4); a00 < a00_end_; ++a00)
      for (int a01 = (a00 + 1), a01_end_ = (4); a01 < a01_end_; ++a01)
        for (int a10 = (0), a10_end_ = (4); a10 < a10_end_; ++a10)
          if (a10 != a00 && a10 != a01) {
            for (int a11 = (a10 + 1), a11_end_ = (4); a11 < a11_end_; ++a11)
              if (a11 != a00 && a11 != a01) {
                int t[2][2];
                t[0][0] = a00;
                t[0][1] = a01;
                t[1][0] = a10;
                t[1][1] = a11;
                int total = 0;
                for (int i = (0), i_end_ = (n); i < i_end_; ++i) {
                  int bestj = -1;
                  int Maxj = -1;
                  for (int j = (0), j_end_ = (2); j < j_end_; ++j) {
                    int cnt = 0;
                    for (int k = (0), k_end_ = (m); k < k_end_; ++k) {
                      int first = t[i & 1][(k ^ j) & 1];
                      if (first == a[i][k]) ++cnt;
                    }
                    if (chkmax(Maxj, cnt)) bestj = j;
                  }
                  total += Maxj;
                  for (int k = (0), k_end_ = (m); k < k_end_; ++k)
                    tmp[i][k] = t[i & 1][(k ^ bestj) & 1];
                }
                if (chkmax(Max, total)) {
                  ans_flip = flip;
                  for (int i = (0), i_end_ = (n); i < i_end_; ++i)
                    ans[i] = tmp[i];
                }
              }
          }
    transpose(a);
    swap(n, m);
  }
  if (ans_flip) swap(n, m), transpose(ans), swap(n, m);
  for (int i = (0), i_end_ = (n); i < i_end_; ++i) {
    for (int j = (0), j_end_ = (m); j < j_end_; ++j) putchar(i2c(ans[i][j]));
    printf("\n");
  }
  return 0;
}
