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;
pair<int, vector<vector<char> > > solve(vector<vector<char> > mat) {
  int n = mat.size(), m = mat[0].size();
  vector<char> g = {'A', 'C', 'G', 'T'};
  vector<vector<char> > best = mat;
  int bestans = 1000000;
  do {
    vector<vector<char> > cur = mat;
    int ans = 0;
    for (int i = 0; i < n; i++) {
      int a = 0, b = 0;
      for (int j = 0; j < m; j++) {
        if (i & 1) {
          if (mat[i][j] != g[j & 1]) a++;
          if (mat[i][j] != g[(j & 1) ^ 1]) b++;
        } else {
          if (mat[i][j] != g[2 + (j & 1)]) a++;
          if (mat[i][j] != g[2 + ((j & 1) ^ 1)]) b++;
        }
      }
      if (a < b) {
        ans += a;
        for (int j = 0; j < m; j++) {
          if (i & 1) {
            cur[i][j] = g[j & 1];
          } else {
            cur[i][j] = g[2 + (j & 1)];
          }
        }
      } else {
        ans += b;
        for (int j = 0; j < m; j++) {
          if (i & 1) {
            cur[i][j] = g[(j & 1) ^ 1];
          } else {
            cur[i][j] = g[2 + ((j & 1) ^ 1)];
          }
        }
      }
    }
    if (ans < bestans) best.swap(cur), bestans = ans;
  } while (next_permutation(g.begin(), g.end()));
  return {bestans, best};
}
signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int n, m;
  cin >> n >> m;
  vector<vector<char> > mat(n, vector<char>(m));
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      cin >> mat[i][j];
    }
  }
  pair<int, vector<vector<char> > > ans1 = solve(mat);
  vector<vector<char> > tmat(m, vector<char>(n));
  for (int i = 0; i < m; i++) {
    for (int j = 0; j < n; j++) {
      tmat[i][j] = mat[j][i];
    }
  }
  pair<int, vector<vector<char> > > ans2 = solve(tmat);
  if (ans1.first < ans2.first) {
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        cout << ans1.second[i][j];
      }
      cout << "\n";
    }
  } else {
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        cout << ans2.second[j][i];
      }
      cout << "\n";
    }
  }
}
