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;
int n, m;
string s[300005];
string q[300005];
string make(char a, char b) {
  string res;
  res += a;
  res += b;
  return res;
}
int sol(bool f, int mx) {
  int ans = 1000000007;
  string w = "ACGT";
  do {
    string a[2][2] = {{make(w[0], w[1]), make(w[1], w[0])},
                      {make(w[2], w[3]), make(w[3], w[2])}};
    int cur = 0;
    for (int i = 0; i < n; i++) {
      int cnt[2] = {0, 0};
      for (int j = 0; j < m; j++) {
        for (int k = 0; k < 2; k++) {
          cnt[k] += s[i][j] != a[i % 2][k][j % 2];
        }
      }
      cur += min(cnt[0], cnt[1]);
    }
    ans = min(ans, cur);
    if (f and mx == ans) {
      for (int i = 0; i < n; i++) {
        int cnt[2] = {0, 0};
        for (int j = 0; j < m; j++) {
          for (int k = 0; k < 2; k++) {
            cnt[k] += s[i][j] != a[i % 2][k][j % 2];
          }
        }
        if (cnt[0] < cnt[1]) {
          for (int j = 0; j < m; j++) {
            s[i][j] = a[i % 2][0][j % 2];
          }
        } else {
          for (int j = 0; j < m; j++) {
            s[i][j] = a[i % 2][1][j % 2];
          }
        }
      }
      return 1;
    }
    cur = 0;
    for (int i = 0; i < m; i++) {
      int cnt[2] = {0, 0};
      for (int j = 0; j < n; j++) {
        for (int k = 0; k < 2; k++) {
          cnt[k] += s[j][i] != a[i % 2][k][j % 2];
        }
      }
      cur += min(cnt[0], cnt[1]);
    }
    ans = min(ans, cur);
    if (f and mx == ans) {
      for (int i = 0; i < m; i++) {
        int cnt[2] = {0, 0};
        for (int j = 0; j < n; j++) {
          for (int k = 0; k < 2; k++) {
            cnt[k] += s[j][i] != a[i % 2][k][j % 2];
          }
        }
        if (cnt[0] < cnt[1]) {
          for (int j = 0; j < n; j++) {
            s[j][i] = a[i % 2][0][j % 2];
          }
        } else {
          for (int j = 0; j < n; j++) {
            s[j][i] = a[i % 2][1][j % 2];
          }
        }
      }
      return 1;
    }
  } while (next_permutation((w).begin(), (w).end()));
  return ans;
}
void solve() {
  cin >> n >> m;
  for (int i = 0; i < n; i++) cin >> s[i], q[i] = s[i];
  int ans = sol(0, 0);
  sol(1, ans);
  for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++) ans -= q[i][j] != s[i][j];
  assert(ans == 0);
  for (int i = 0; i < n; i++) cout << s[i] << '\n';
}
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int t = 1;
  while (t--) {
    solve();
  }
  return 0;
}
