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;
struct mat {
  int n, m;
  vector<char> data;
  mat(int n, int m) : n(n), m(m), data(n * m) {}
  char& get(int i, int j, int rot = 0) {
    return data[!rot ? (i * m + j) : (j * m + i)];
  }
  void dump() {
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        cout << get(i, j);
      }
      cout << "\n";
    }
  }
};
int main() {
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  int n, m;
  cin >> n >> m;
  mat g(n, m);
  for (int i = 0; i < n; i++) {
    string s;
    cin >> s;
    for (int j = 0; j < m; j++) {
      g.get(i, j) = s[j];
    }
  }
  string seed = "ACGT";
  mat best = g;
  int bestv = -1;
  mat cur(n, m);
  do {
    int N = n, M = m;
    for (int rot = 0; rot < 2; rot++) {
      int val = 0;
      for (int i = 0; i < N; i++) {
        int c[2];
        c[0] = c[1] = 0;
        for (int j = 0; j < M; j++) {
          for (int k = 0; k < 2; k++) {
            c[k] += seed[(i % 2) * 2 + (j + k) % 2] == g.get(i, j, rot);
          }
        }
        int k = c[1] > c[0];
        for (int j = 0; j < M; j++) {
          cur.get(i, j, rot) = seed[(i % 2) * 2 + (j + k) % 2];
        }
        if (0) cout << c[k] << endl;
        val += c[k];
      }
      if (0) {
        cur.dump();
        cout << val << "\n" << endl;
      }
      if (val > bestv) {
        bestv = val;
        best = cur;
      }
      swap(N, M);
    }
  } while (next_permutation(seed.begin(), seed.end()));
  best.dump();
  return 0;
}
