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>
std::string c = "ATGC";
std::vector<std::string> ans, tmp, s;
int min = INT_MAX, now = 0;
int main(int argc, char *argv[]) {
  int n, m;
  scanf("%d %d", &n, &m);
  for (int i = 0; i < n; i++) {
    std::string str;
    std::cin >> str;
    s.push_back(str);
  }
  for (int c1 = 0; c1 < 4; c1++) {
    for (int c2 = c1 + 1; c2 < 4; c2++) {
      std::string t;
      std::set<int> set;
      for (int i = 0; i < 4; i++) set.insert(i);
      set.erase(c1), set.erase(c2);
      std::set<int>::iterator it = set.begin();
      t += c[c1], t += c[c2], t += c[*(it++)], t += c[*it];
      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] += t[b + (j & 1)];
          }
        } else {
          for (int j = 0; j < m; j++) {
            tmp[i] += t[b + ((j & 1) ^ 1)];
          }
        }
        now += std::min(cnt1, cnt2);
      }
      if (now < min) {
        min = now;
        ans = tmp;
      }
      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] += t[b + (i & 1)];
          }
        } else {
          for (int i = 0; i < n; i++) {
            tmp[i] += t[b + ((i & 1) ^ 1)];
          }
        }
        now += std::min(cnt1, cnt2);
      }
      if (now < min) {
        min = now;
        ans = tmp;
      }
    }
  }
  for (int i = 0; i < n; i++) {
    std::cout << ans[i] << std::endl;
  }
  return 0;
}
