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>
const int INF = 0x3f3f3f3f;
const std::string str = "ATGC";
int main() {
  int n, m;
  std::vector<std::string> s;
  std::vector<std::string> tmp;
  std::vector<std::string> ans;
  int min_ans = INF, pos;
  std::cin >> n >> m;
  for (int i = 0; i < n; ++i) {
    std::string st;
    std::cin >> st;
    s.push_back(st);
  }
  for (int c1 = 0; c1 < 4; ++c1)
    for (int c2 = c1 + 1; c2 < 4; ++c2) {
      std::string stri;
      std::set<int> st;
      for (int i = 0; i < 4; ++i) st.insert(i);
      st.erase(c1);
      st.erase(c2);
      auto it = st.begin();
      stri.push_back(str[c1]);
      stri.push_back(str[c2]);
      stri.push_back(str[*(it++)]);
      stri.push_back(str[*it]);
      pos = 0;
      tmp.clear();
      for (int i = 0; i < n; ++i) {
        tmp.push_back("");
        int bit = (i & 1) << 1;
        int cnt1 = 0, cnt2 = 0;
        for (int j = 0; j < m; ++j) {
          if (s[i][j] != stri[bit + (j & 1)]) ++cnt1;
          if (s[i][j] != stri[bit + ((j & 1) ^ 1)]) ++cnt2;
        }
        if (cnt1 < cnt2)
          for (int j = 0; j < m; ++j) tmp[i].push_back(stri[bit + (j & 1)]);
        else
          for (int j = 0; j < m; ++j)
            tmp[i].push_back(stri[bit + ((j & 1) ^ 1)]);
        pos += std::min(cnt1, cnt2);
      }
      if (pos < min_ans) {
        ans = tmp;
        min_ans = pos;
      }
      pos = 0;
      tmp.clear();
      for (int i = 0; i < n; ++i) tmp.push_back("");
      for (int j = 0; j < m; ++j) {
        int bit = (j & 1) << 1;
        int cnt1 = 0, cnt2 = 0;
        for (int i = 0; i < n; ++i) {
          if (s[i][j] != stri[bit + (i & 1)]) ++cnt1;
          if (s[i][j] != stri[bit + ((i & 1) ^ 1)]) ++cnt2;
        }
        if (cnt1 < cnt2)
          for (int i = 0; i < n; ++i) tmp[i].push_back(stri[bit + (i & 1)]);
        else
          for (int i = 0; i < n; ++i)
            tmp[i].push_back(stri[bit + ((i & 1) ^ 1)]);
        pos += std::min(cnt1, cnt2);
      }
      if (pos < min_ans) {
        ans = tmp;
        min_ans = pos;
      }
    }
  for (int i = 0; i < n; ++i) std::cout << ans[i] << std::endl;
  return 0;
}
