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 MX = 300005;
string ans[MX];
string s[MX];
int n, m;
string cur[MX];
int calcRow(int i, string S) {
  int res = 0;
  for (int j = 0; j < m; j++) {
    res += (s[i][j] != S[j % 2]);
  }
  return res;
}
void paintRow(int i, string S) {
  for (int j = 0; j < m; j++) {
    cur[i][j] = S[j % 2];
  }
}
int calcColumn(int j, string S) {
  int res = 0;
  for (int i = 0; i < n; i++) {
    res += (s[i][j] != S[i % 2]);
  }
  return res;
}
void paintColumn(int j, string S) {
  for (int i = 0; i < n; i++) {
    cur[i][j] = S[i % 2];
  }
}
int calcVert(string S1, string S2) {
  string S1_rev = S1;
  reverse(S1_rev.begin(), S1_rev.end());
  string S2_rev = S2;
  reverse(S2_rev.begin(), S2_rev.end());
  int total = 0;
  for (int j = 0; j < m; j += 2) {
    int s1 = calcColumn(j, S1);
    int s2 = calcColumn(j, S1_rev);
    if (s1 < s2)
      paintColumn(j, S1);
    else
      paintColumn(j, S1_rev);
    total += min(s1, s2);
  }
  for (int j = 1; j < m; j += 2) {
    int s1 = calcColumn(j, S2);
    int s2 = calcColumn(j, S2_rev);
    if (s1 < s2)
      paintColumn(j, S2);
    else
      paintColumn(j, S2_rev);
    total += min(s1, s2);
  }
  return total;
}
int calcHoriz(string S1, string S2) {
  string S1_rev = S1;
  reverse(S1_rev.begin(), S1_rev.end());
  string S2_rev = S2;
  reverse(S2_rev.begin(), S2_rev.end());
  int total = 0;
  for (int i = 0; i < n; i += 2) {
    int s1 = calcRow(i, S1);
    int s2 = calcRow(i, S1_rev);
    if (s1 < s2)
      paintRow(i, S1);
    else
      paintRow(i, S1_rev);
    total += min(s1, s2);
  }
  for (int i = 1; i < n; i += 2) {
    int s1 = calcRow(i, S2);
    int s2 = calcRow(i, S2_rev);
    if (s1 < s2)
      paintRow(i, S2);
    else
      paintRow(i, S2_rev);
    total += min(s1, s2);
  }
  return total;
}
string SS1[6];
string SS2[6];
int main() {
  SS1[0] = "AT";
  SS1[1] = "AC";
  SS1[2] = "AG";
  SS1[3] = "CT";
  SS1[4] = "CG";
  SS1[5] = "TG";
  SS2[0] = "CG";
  SS2[1] = "TG";
  SS2[2] = "TC";
  SS2[3] = "AG";
  SS2[4] = "AT";
  SS2[5] = "AC";
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n >> m;
  for (int i = 0; i < n; i++) {
    cin >> s[i];
    cur[i].resize(m);
  }
  int mn = n * m;
  for (int i = 0; i < 6; i++) {
    int tmp = calcVert(SS1[i], SS2[i]);
    if (tmp <= mn) {
      mn = tmp;
      for (int j = 0; j < n; j++) {
        ans[j] = cur[j];
      }
    }
  }
  for (int i = 0; i < 6; i++) {
    int tmp = calcHoriz(SS1[i], SS2[i]);
    if (tmp <= mn) {
      mn = tmp;
      for (int j = 0; j < n; j++) {
        ans[j] = cur[j];
      }
    }
  }
  for (int i = 0; i < n; i++) {
    cout << ans[i] << "\n";
  }
}
