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 U, class T>
void Max(U &first, T second) {
  if (first < second) first = second;
}
template <class U, class T>
void Min(U &first, T second) {
  if (first > second) first = second;
}
template <class T>
void add(int &a, T b) {
  a = (a + b) % 1000000007;
}
inline int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
inline long long gcd(long long a, long long b) {
  return b == 0 ? a : gcd(b, a % b);
}
int pow(int a, int b) {
  int ans = 1;
  while (b) {
    if (b & 1) ans = 1LL * ans * a % 1000000007;
    a = 1LL * a * a % 1000000007;
    b >>= 1;
  }
  return ans;
}
int pow(int a, int b, int c) {
  int ans = 1;
  while (b) {
    if (b & 1) ans = 1LL * ans * a % c;
    a = 1LL * a * a % c;
    b >>= 1;
  }
  return ans;
}
string s[300010];
pair<int, int> f[16][300010];
char ch[] = "AGCT", g[2];
int solve(int n, int m, vector<string> &t, int rev = 0) {
  for (int i = 0; i < 16; i++) {
    if (__builtin_popcount(i) == 2) {
      int first = -1, second;
      for (int j = 0; j < 4; j++)
        if (i >> j & 1) {
          if (first == -1)
            first = j;
          else
            second = j;
        }
      g[0] = ch[first], g[1] = ch[second];
      for (int l = 0; l < n; l++) {
        int a = 0, b = 0;
        if (rev == 0)
          for (int r = 0; r < m; r++)
            a += (s[l][r] != g[r & 1]), b += (s[l][r] != g[!(r & 1)]);
        else
          for (int r = 0; r < m; r++)
            a += (s[r][l] != g[r & 1]), b += (s[r][l] != g[!(r & 1)]);
        if (a <= b)
          f[i][l] = {0, a};
        else
          f[i][l] = {1, b};
      }
    }
  }
  int ans = -1, p;
  for (int i = 0; i < 16; i++) {
    if (__builtin_popcount(i) == 2) {
      int j = 15 - i;
      int res = 0;
      for (int k = 0; k < n; k++)
        res += k % 2 == 0 ? f[i][k].second : f[j][k].second;
      if (ans == -1 || ans > res) ans = res, p = i;
    }
  }
  for (int it = 0; it < 2; it++) {
    int first = -1, second;
    for (int i = 0; i < 4; i++)
      if (p >> i & 1) {
        if (first == -1)
          first = i;
        else
          second = i;
      }
    for (int i = it; i < n; i++) {
      if (f[p][i].first == 0) {
        g[0] = ch[first], g[1] = ch[second];
      } else {
        g[0] = ch[second], g[1] = ch[first];
      }
      if (rev == 0)
        for (int j = 0; j < m; j++) t[i][j] = g[j & 1];
      else
        for (int j = 0; j < m; j++) t[j][i] = g[j & 1];
      i++;
    }
    p = 15 - p;
  }
  return ans;
}
int main() {
  int ca = 0, T, k, i, j, m = 0, K, n;
  double start = clock();
  scanf("%d%d", &n, &m);
  for (int i = 0; i < n; i++) cin >> s[i];
  vector<string> t1(n, string(m, ' ')), t2(n, string(m, ' '));
  int ans1 = solve(n, m, t1);
  int ans2 = solve(m, n, t2, 1);
  if (ans2 < ans1) t1 = t2;
  for (int i = 0; i < n; i++) puts(t1[i].c_str());
  cerr << (1. * clock() - start) / CLOCKS_PER_SEC << "\n";
}
