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;
int n, m, mi, num;
vector<string> t, v, res;
int f(char a, char b, char c, char d, vector<string>& v) {
  char x, y;
  for (int i = 0; i < n; ++i) {
    if (i % 2) {
      x = c;
      y = d;
    } else {
      x = a;
      y = b;
    }
    int xy = 0;
    int yx = 0;
    for (int j = 0; j < m; ++j) {
      char c = t[i][j];
      if (j % 2 == 0) {
        if (c != x) ++xy;
        if (c != y) ++yx;
      }
      if (j % 2 == 1) {
        if (c != y) ++xy;
        if (c != x) ++yx;
      }
    }
    if (yx < xy) swap(x, y);
    for (int j = 0; j < m; ++j) v[i][j] = (j % 2 == 0 ? x : y);
  }
  num = 0;
  for (int i = 0; i < n; ++i)
    for (int j = 0; j < m; ++j)
      if (v[i][j] != t[i][j]) ++num;
  return num;
}
int g(char a, char b, char c, char d, vector<string>& v) {
  char x, y;
  for (int j = 0; j < m; ++j) {
    if (j % 2) {
      x = c;
      y = d;
    } else {
      x = a;
      y = b;
    }
    int xy = 0;
    int yx = 0;
    for (int i = 0; i < n; ++i) {
      char c = t[i][j];
      if (i % 2 == 0) {
        if (c != x) ++xy;
        if (c != y) ++yx;
      }
      if (i % 2 == 1) {
        if (c != y) ++xy;
        if (c != x) ++yx;
      }
    }
    if (yx < xy) swap(x, y);
    for (int i = 0; i < n; ++i) v[i][j] = (i % 2 == 0 ? x : y);
  }
  num = 0;
  for (int i = 0; i < n; ++i)
    for (int j = 0; j < m; ++j)
      if (v[i][j] != t[i][j]) ++num;
  return num;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin >> n >> m;
  t.resize(n);
  for (int i = 0; i < n; ++i) cin >> t[i];
  v = t;
  mi = n * m + 5;
  if (mi > f('A', 'G', 'C', 'T', v)) {
    mi = num;
    res = v;
  }
  if (mi > f('A', 'C', 'G', 'T', v)) {
    mi = num;
    res = v;
  }
  if (mi > f('A', 'T', 'C', 'G', v)) {
    mi = num;
    res = v;
  }
  if (mi > f('C', 'G', 'A', 'T', v)) {
    mi = num;
    res = v;
  }
  if (mi > f('T', 'G', 'C', 'A', v)) {
    mi = num;
    res = v;
  }
  if (mi > f('C', 'T', 'A', 'G', v)) {
    mi = num;
    res = v;
  }
  if (mi > g('A', 'G', 'C', 'T', v)) {
    mi = num;
    res = v;
  }
  if (mi > g('A', 'C', 'G', 'T', v)) {
    mi = num;
    res = v;
  }
  if (mi > g('A', 'T', 'C', 'G', v)) {
    mi = num;
    res = v;
  }
  if (mi > g('C', 'G', 'A', 'T', v)) {
    mi = num;
    res = v;
  }
  if (mi > g('T', 'G', 'C', 'A', v)) {
    mi = num;
    res = v;
  }
  if (mi > g('C', 'T', 'A', 'G', v)) {
    mi = num;
    res = v;
  }
  for (int i = 0; i < n; ++i) cout << res[i] << "\n";
  return 0;
}
