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;
vector<char> w = {'A', 'T', 'G', 'C'};
pair<int, vector<vector<int> > > solve(const vector<string> &a) {
  int n = a.size();
  int m = a[0].size();
  int cost[4][4][m][2];
  memset(cost, 0, sizeof(cost));
  for (int i = 0; i < 4; i++) {
    for (int j = 0; j < 4; j++) {
      if (i == j) continue;
      for (int c = 0; c < m; c++) {
        for (int r = 0; r < n; r++) {
          if (r % 2 == 0) {
            cost[i][j][c][0] += a[r][c] != w[i];
            cost[i][j][c][1] += a[r][c] != w[j];
          } else {
            cost[i][j][c][0] += a[r][c] != w[j];
            cost[i][j][c][1] += a[r][c] != w[i];
          }
        }
      }
    }
  }
  int ans = 1e9;
  for (int a = 0; a < 4; a++) {
    for (int b = 0; b < 4; b++) {
      for (int c = 0; c < 4; c++) {
        for (int d = 0; d < 4; d++) {
          set<int> s = {a, b, c, d};
          if (s.size() != 4) continue;
          int res = 0;
          for (int i = 0; i < m; i++) {
            if (i % 2 == 0) {
              if (cost[a][b][i][0] < cost[a][b][i][1])
                res += cost[a][b][i][0];
              else
                res += cost[a][b][i][1];
            } else {
              if (cost[c][d][i][0] < cost[c][d][i][1])
                res += cost[c][d][i][0];
              else
                res += cost[c][d][i][1];
            }
          }
          ans = min(ans, res);
        }
      }
    }
  }
  vector<vector<int> > mat(n, vector<int>(m));
  for (int a = 0; a < 4; a++) {
    for (int b = 0; b < 4; b++) {
      for (int c = 0; c < 4; c++) {
        for (int d = 0; d < 4; d++) {
          set<int> s = {a, b, c, d};
          if (s.size() != 4) continue;
          int res = 0;
          for (int i = 0; i < m; i++) {
            if (i % 2 == 0) {
              if (cost[a][b][i][0] < cost[a][b][i][1])
                res += cost[a][b][i][0];
              else
                res += cost[a][b][i][1];
            } else {
              if (cost[c][d][i][0] < cost[c][d][i][1])
                res += cost[c][d][i][0];
              else
                res += cost[c][d][i][1];
            }
          }
          if (res == ans) {
            for (int i = 0; i < m; i++) {
              if (i % 2 == 0) {
                if (cost[a][b][i][0] < cost[a][b][i][1]) {
                  for (int j = 0; j < n; j++) {
                    if (j % 2 == 0)
                      mat[j][i] = a;
                    else
                      mat[j][i] = b;
                  }
                } else {
                  for (int j = 0; j < n; j++) {
                    if (j % 2 == 0)
                      mat[j][i] = b;
                    else
                      mat[j][i] = a;
                  }
                }
              } else {
                if (cost[c][d][i][0] < cost[c][d][i][1]) {
                  for (int j = 0; j < n; j++) {
                    if (j % 2 == 0)
                      mat[j][i] = c;
                    else
                      mat[j][i] = d;
                  }
                } else {
                  for (int j = 0; j < n; j++) {
                    if (j % 2 == 0)
                      mat[j][i] = d;
                    else
                      mat[j][i] = c;
                  }
                }
              }
            }
          }
        }
      }
    }
  }
  return {ans, mat};
}
vector<string> rotate(const vector<string> &a) {
  vector<string> b(a[0].size(), string(a.size(), 'A'));
  for (int i = 0; i < a.size(); i++) {
    for (int j = 0; j < a[0].size(); j++) {
      b[j][i] = a[i][j];
    }
  }
  return b;
}
int main() {
  int n, m;
  cin >> n >> m;
  vector<string> a(n);
  for (int i = 0; i < n; i++) cin >> a[i];
  auto x = solve(a);
  a = rotate(a);
  auto y = solve(a);
  int flip = 0;
  if (x.first > y.first) {
    swap(x, y);
    flip = 1;
  }
  auto mat = x.second;
  vector<string> ans(mat.size(), string(mat[0].size(), 'A'));
  for (int i = 0; i < mat.size(); i++)
    for (int j = 0; j < mat[0].size(); j++) ans[i][j] = w[mat[i][j]];
  if (flip) {
    ans = rotate(ans);
    ans = rotate(ans);
    ans = rotate(ans);
  }
  for (int i = 0; i < ans.size(); i++) {
    printf("%s\n", ans[i].c_str());
  }
  return 0;
}
