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;
inline void fastio() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
}
long long n, m;
vector<vector<long long> > v;
void init() {
  cin >> n >> m;
  v.assign(n, vector<long long>(m, 0));
  for (long long i = 0; i < n; ++i) {
    for (long long j = 0; j < m; ++j) {
      char c;
      cin >> c;
      if (c == 'A') {
        v[i][j] = 0;
      } else if (c == 'G') {
        v[i][j] = 1;
      } else if (c == 'T') {
        v[i][j] = 2;
      } else {
        v[i][j] = 3;
      }
    }
  }
}
long long answer = 0;
long long av, ah;
vector<vector<long long> > ans1;
vector<vector<long long> > ans2;
void tr(const vector<long long>& p, vector<vector<long long> >& ans,
        long long& aa) {
  long long ret = 0;
  for (long long i = 0; i < n; ++i) {
    if (i % 2 == 0) {
      long long a1 = 0, a2 = 0;
      for (long long j = 0; j < m; ++j) {
        if (j % 2 == 0 && v[i][j] != p[0]) a1++;
        if (j % 2 == 1 && v[i][j] != p[1]) a1++;
        if (j % 2 == 0 && v[i][j] != p[1]) a2++;
        if (j % 2 == 1 && v[i][j] != p[0]) a2++;
      }
      ret += min(a1, a2);
    } else {
      long long a1 = 0, a2 = 0;
      for (long long j = 0; j < m; ++j) {
        if (j % 2 == 0 && v[i][j] != p[2]) a1++;
        if (j % 2 == 1 && v[i][j] != p[3]) a1++;
        if (j % 2 == 0 && v[i][j] != p[3]) a2++;
        if (j % 2 == 1 && v[i][j] != p[2]) a2++;
      }
      ret += min(a1, a2);
    }
  }
  if (ret < aa) {
    aa = ret;
    for (long long i = 0; i < n; ++i) {
      if (i % 2 == 0) {
        long long a1 = 0, a2 = 0;
        for (long long j = 0; j < m; ++j) {
          if (j % 2 == 0 && v[i][j] != p[0]) a1++;
          if (j % 2 == 1 && v[i][j] != p[1]) a1++;
          if (j % 2 == 0 && v[i][j] != p[1]) a2++;
          if (j % 2 == 1 && v[i][j] != p[0]) a2++;
        }
        if (a1 < a2) {
          for (long long j = 0; j < m; ++j) {
            if (j % 2 == 0) {
              ans[i][j] = p[0];
            } else {
              ans[i][j] = p[1];
            }
          }
        } else {
          for (long long j = 0; j < m; ++j) {
            if (j % 2 == 0) {
              ans[i][j] = p[1];
            } else {
              ans[i][j] = p[0];
            }
          }
        }
      } else {
        long long a1 = 0, a2 = 0;
        for (long long j = 0; j < m; ++j) {
          if (j % 2 == 0 && v[i][j] != p[2]) a1++;
          if (j % 2 == 1 && v[i][j] != p[3]) a1++;
          if (j % 2 == 0 && v[i][j] != p[3]) a2++;
          if (j % 2 == 1 && v[i][j] != p[2]) a2++;
        }
        if (a1 < a2) {
          for (long long j = 0; j < m; ++j) {
            if (j % 2 == 0) {
              ans[i][j] = p[2];
            } else {
              ans[i][j] = p[3];
            }
          }
        } else {
          for (long long j = 0; j < m; ++j) {
            if (j % 2 == 0) {
              ans[i][j] = p[3];
            } else {
              ans[i][j] = p[2];
            }
          }
        }
      }
    }
  }
}
map<long long, char> mp;
void solve() {
  mp[0] = 'A';
  mp[1] = 'G';
  mp[2] = 'T';
  mp[3] = 'C';
  init();
  answer = n * m;
  av = n * m;
  ah = n * m;
  vector<long long> p = {0, 1, 2, 3};
  vector<vector<long long> > vert = v;
  do {
    tr(p, vert, av);
  } while (next_permutation(p.begin(), p.end()));
  vector<vector<long long> > nv(m, vector<long long>(n, 0));
  for (long long i = 0; i < n; ++i) {
    for (long long j = 0; j < m; ++j) {
      nv[j][i] = v[i][j];
    }
  }
  swap(n, m);
  v.swap(nv);
  p = {0, 1, 2, 3};
  vector<vector<long long> > hor = v;
  do {
    tr(p, hor, ah);
  } while (next_permutation(p.begin(), p.end()));
  swap(n, m);
  if (av < ah) {
    for (long long i = 0; i < n; ++i) {
      for (long long j = 0; j < m; ++j) {
        cout << mp[vert[i][j]];
      }
      cout << '\n';
    }
  } else {
    for (long long i = 0; i < n; ++i) {
      for (long long j = 0; j < m; ++j) {
        cout << mp[hor[j][i]];
      }
      cout << '\n';
    }
  }
}
signed main() {
  fastio();
  long long t = 1;
  while (t--) {
    solve();
  }
  return 0;
}
