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;
long long gcd(long long a, long long b) { return b == 0 ? a : gcd(b, a % b); }
long long qpow(long long a, long long b, long long m) {
  long long r = 1;
  a %= m;
  for (; b; b >>= 1) {
    if (b & 1) r = r * a % m;
    a = a * a % m;
  }
  return r;
}
const int inf = 0x7fffffff;
int cnt[40];
char aa[] = "ATCG";
string s[300005];
string ans[300005];
int n, m;
int main() {
  ios::sync_with_stdio(false);
  cin >> n >> m;
  for (int i = 0; i < n; i++) cin >> s[i];
  int tt = 0, pos = 0, mi = inf;
  for (int i1 = 0; i1 < 4; i1++) {
    for (int i2 = i1 + 1; i2 < 4; i2++) {
      vector<int> ve[2];
      ve[0].push_back(i1);
      ve[0].push_back(i2);
      for (int i = 0; i < 4; i++)
        if (i != i1 && i != i2) ve[1].push_back(i);
      tt++;
      for (int i = 0; i < n; i++) {
        int p = i % 2;
        int x = 0, cnt1 = 0, cnt2 = 0;
        for (int j = 0; j < m; j++) {
          if (aa[ve[p][x]] != s[i][j]) cnt1++;
          x ^= 1;
        }
        x = 1;
        for (int j = 0; j < m; j++) {
          if (aa[ve[p][x]] != s[i][j]) cnt2++;
          x ^= 1;
        }
        if (cnt1 < cnt2)
          cnt[tt] += cnt1;
        else
          cnt[tt] += cnt2;
      }
      if (cnt[tt] < mi) {
        mi = cnt[tt];
        pos = tt;
      }
      tt++;
      for (int i = 0; i < n; i++) {
        int p = (i + 1) % 2;
        int x = 0, cnt1 = 0, cnt2 = 0;
        for (int j = 0; j < m; j++) {
          if (aa[ve[p][x]] != s[i][j]) cnt1++;
          x ^= 1;
        }
        x = 1;
        for (int j = 0; j < m; j++) {
          if (aa[ve[p][x]] != s[i][j]) cnt2++;
          x ^= 1;
        }
        if (cnt1 < cnt2)
          cnt[tt] += cnt1;
        else
          cnt[tt] += cnt2;
      }
      if (cnt[tt] < mi) {
        mi = cnt[tt];
        pos = tt;
      }
      tt++;
      for (int i = 0; i < m; i++) {
        int p = i % 2;
        int x = 0, cnt1 = 0, cnt2 = 0;
        for (int j = 0; j < n; j++) {
          if (aa[ve[p][x]] != s[j][i]) cnt1++;
          x ^= 1;
        }
        x = 1;
        for (int j = 0; j < n; j++) {
          if (aa[ve[p][x]] != s[j][i]) cnt2++;
          x ^= 1;
        }
        if (cnt1 < cnt2)
          cnt[tt] += cnt1;
        else
          cnt[tt] += cnt2;
      }
      if (cnt[tt] < mi) {
        mi = cnt[tt];
        pos = tt;
      }
      tt++;
      for (int i = 0; i < m; i++) {
        int p = (i + 1) % 2;
        int x = 0, cnt1 = 0, cnt2 = 0;
        for (int j = 0; j < n; j++) {
          if (aa[ve[p][x]] != s[j][i]) cnt1++;
          x ^= 1;
        }
        x = 1;
        for (int j = 0; j < n; j++) {
          if (aa[ve[p][x]] != s[j][i]) cnt2++;
          x ^= 1;
        }
        if (cnt1 < cnt2)
          cnt[tt] += cnt1;
        else
          cnt[tt] += cnt2;
      }
      if (cnt[tt] < mi) {
        mi = cnt[tt];
        pos = tt;
      }
    }
  }
  int ttt = 0;
  for (int i1 = 0; i1 < 4; i1++) {
    for (int i2 = i1 + 1; i2 < 4; i2++) {
      vector<int> ve[2];
      ve[0].push_back(i1);
      ve[0].push_back(i2);
      for (int i = 0; i < 4; i++)
        if (i != i1 && i != i2) ve[1].push_back(i);
      ttt++;
      if (ttt == pos) {
        for (int i = 0; i < n; i++) {
          int p = i % 2;
          int x = 0, cnt1 = 0, cnt2 = 0;
          string s1 = "", s2 = "";
          for (int j = 0; j < m; j++) {
            s1 += aa[ve[p][x]];
            if (aa[ve[p][x]] != s[i][j]) cnt1++;
            x ^= 1;
          }
          x = 1;
          for (int j = 0; j < m; j++) {
            s2 += aa[ve[p][x]];
            if (aa[ve[p][x]] != s[i][j]) cnt2++;
            x ^= 1;
          }
          if (cnt1 < cnt2)
            cout << s1 << endl;
          else
            cout << s2 << endl;
        }
        return 0;
      }
      ttt++;
      if (ttt == pos) {
        for (int i = 0; i < n; i++) {
          int p = (i + 1) % 2;
          int x = 0, cnt1 = 0, cnt2 = 0;
          string s1 = "", s2 = "";
          for (int j = 0; j < m; j++) {
            s1 += aa[ve[p][x]];
            if (aa[ve[p][x]] != s[i][j]) cnt1++;
            x ^= 1;
          }
          x = 1;
          for (int j = 0; j < m; j++) {
            s2 += aa[ve[p][x]];
            if (aa[ve[p][x]] != s[i][j]) cnt2++;
            x ^= 1;
          }
          if (cnt1 < cnt2)
            cout << s1 << endl;
          else
            cout << s2 << endl;
        }
        return 0;
      }
      ttt++;
      if (ttt == pos) {
        for (int i = 0; i < m; i++) {
          int p = i % 2;
          int x = 0, cnt1 = 0, cnt2 = 0;
          string s1 = "", s2 = "";
          for (int j = 0; j < n; j++) {
            s1 += aa[ve[p][x]];
            if (aa[ve[p][x]] != s[j][i]) cnt1++;
            x ^= 1;
          }
          x = 1;
          for (int j = 0; j < n; j++) {
            s2 += aa[ve[p][x]];
            if (aa[ve[p][x]] != s[j][i]) cnt2++;
            x ^= 1;
          }
          if (cnt1 < cnt2) {
            for (int j = 0; j < n; j++) ans[j] += s1[j];
          } else {
            for (int j = 0; j < n; j++) ans[j] += s2[j];
          }
        }
        for (int i = 0; i < n; i++) cout << ans[i] << endl;
        return 0;
      }
      ttt++;
      if (ttt == pos) {
        for (int i = 0; i < m; i++) {
          int p = (i + 1) % 2;
          int x = 0, cnt1 = 0, cnt2 = 0;
          string s1 = "", s2 = "";
          for (int j = 0; j < n; j++) {
            s1 += aa[ve[p][x]];
            if (aa[ve[p][x]] != s[j][i]) cnt1++;
            x ^= 1;
          }
          x = 1;
          for (int j = 0; j < n; j++) {
            s2 += aa[ve[p][x]];
            if (aa[ve[p][x]] != s[j][i]) cnt2++;
            x ^= 1;
          }
          if (cnt1 < cnt2) {
            for (int j = 0; j < n; j++) ans[j] += s1[j];
          } else {
            for (int j = 0; j < n; j++) ans[j] += s2[j];
          }
        }
        for (int i = 0; i < n; i++) cout << ans[i] << endl;
        return 0;
      }
    }
  }
  return 0;
}
