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;
const int N = 1e6 + 10;
const long long inf = 1e9 + 10;
const long long mod = 1e9 + 7;
const string str = "ATGC";
vector<string> s, tmp, ans;
int main() {
  int n, m;
  cin >> n >> m;
  for (int i = 0; i < n; i++) {
    string st;
    cin >> st;
    s.push_back(st);
  }
  int ansmin = inf, now;
  for (int c1 = 0; c1 < 4; c1++) {
    for (int c2 = c1 + 1; c2 < 4; c2++) {
      string t;
      t.push_back(str[c1]);
      t.push_back(str[c2]);
      for (int i = 0; i < 4; i++)
        if (i != c1 && i != c2) t.push_back(str[i]);
      now = 0;
      tmp.clear();
      for (int i = 0; i < n; i++) {
        tmp.push_back("");
        int b = (i & 1) << 1;
        int cnt1 = 0, cnt2 = 0;
        for (int j = 0; j < m; j++) {
          if (s[i][j] != t[b + (j & 1)]) ++cnt1;
          if (s[i][j] != t[b + (j & 1) ^ 1]) ++cnt2;
        }
        if (cnt1 < cnt2)
          for (int j = 0; j < m; j++) tmp[i].push_back(t[b + (j & 1)]);
        else
          for (int j = 0; j < m; j++) tmp[i].push_back(t[b + ((j & 1) ^ 1)]);
        now += min(cnt1, cnt2);
      }
      if (now < ansmin) {
        ans = tmp;
        ansmin = now;
      }
      now = 0;
      tmp.clear();
      for (int i = 0; i < n; i++) tmp.push_back("");
      for (int j = 0; j < m; j++) {
        int b = (j & 1) << 1;
        int cnt1 = 0, cnt2 = 0;
        for (int i = 0; i < n; i++) {
          if (s[i][j] != t[b + (i & 1)]) ++cnt1;
          if (s[i][j] != t[b + (i & 1) ^ 1]) ++cnt2;
        }
        if (cnt1 < cnt2)
          for (int i = 0; i < n; i++) tmp[i].push_back(t[b + (i & 1)]);
        else
          for (int i = 0; i < n; i++) tmp[i].push_back(t[b + ((i & 1) ^ 1)]);
        now += min(cnt1, cnt2);
      }
      if (now < ansmin) {
        ans = tmp;
        ansmin = now;
      }
    }
  }
  for (int i = 0; i < n; i++) cout << ans[i] << endl;
}
