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;
using ll = long long;
int n, m;
pair<int, vector<vector<char>>> solve(vector<vector<char>> v) {
  vector<char> t = {'A', 'C', 'T', 'G'};
  int gans = 1e9;
  vector<vector<char>> best = v;
  for (char a : t) {
    for (char b : t) {
      if (a == b) continue;
      char c, d;
      for (char c1 : t) {
        if (c1 != a && c1 != b) {
          c = c1;
          break;
        }
      }
      for (char d1 : t) {
        if (d1 != a && d1 != b && d1 != c) {
          d = d1;
          break;
        }
      }
      int ans = 0;
      vector<bool> z(n);
      for (int i = 0; i < n; i++) {
        int ans1 = 0, ans2 = 0;
        for (int j = 0; j < m; j++) {
          if (i % 2 == 0 && j % 2 == 0) {
            ans1 += !(v[i][j] == a);
            ans2 += !(v[i][j] == b);
          }
          if (i % 2 == 0 && j % 2 == 1) {
            ans1 += !(v[i][j] == b);
            ans2 += !(v[i][j] == a);
          }
          if (i % 2 == 1 && j % 2 == 0) {
            ans1 += !(v[i][j] == c);
            ans2 += !(v[i][j] == d);
          }
          if (i % 2 == 1 && j % 2 == 1) {
            ans1 += !(v[i][j] == d);
            ans2 += !(v[i][j] == c);
          }
        }
        ans += min(ans1, ans2);
        z[i] = ans1 > ans2;
      }
      if (ans < gans) {
        gans = ans;
        for (int i = 0; i < n; i++) {
          for (int j = 0; j < m; j++) {
            if (i % 2 == 0) {
              if (z[i])
                best[i][j] = (j % 2 == 0 ? b : a);
              else
                best[i][j] = (j % 2 == 0 ? a : b);
            } else {
              if (z[i])
                best[i][j] = (j % 2 == 0 ? d : c);
              else
                best[i][j] = (j % 2 == 0 ? c : d);
            }
          }
        }
      }
    }
  }
  return {gans, best};
}
int main() {
  cin >> n >> m;
  vector<vector<char>> v(n, vector<char>(m));
  vector<vector<char>> t(m, vector<char>(n));
  for (int i = 0; i < n; i++) {
    string s;
    cin >> s;
    for (int j = 0; j < m; j++) {
      v[i][j] = s[j];
      t[j][i] = s[j];
    }
  }
  auto p1 = solve(v);
  swap(n, m);
  auto p2 = solve(t);
  swap(n, m);
  if (p1.first < p2.first) {
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) cout << p1.second[i][j];
      cout << "\n";
    }
  } else {
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) cout << p2.second[j][i];
      cout << "\n";
    }
  }
}
