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;
char s[300005];
int cnt[2][300005][5];
int id(char c) {
  if (c == 'A') return 0;
  if (c == 'C') return 1;
  if (c == 'G') return 2;
  if (c == 'T') return 3;
}
pair<int, vector<string>> work(vector<string> a) {
  vector<int> p = {0, 1, 2, 3};
  int step = 1e9;
  memset(cnt, 0, sizeof(cnt));
  int n = a.size();
  int m = a[0].length();
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < m; ++j) {
      cnt[i % 2][j][id(a[i][j])] += 1;
      cnt[i % 2][j][4] += 1;
    }
  }
  vector<string> ans;
  char di[5] = "ACGT";
  do {
    int tmp = 0;
    tmp += cnt[0][0][4] - cnt[0][0][p[0]];
    tmp += cnt[0][1][4] - cnt[0][1][p[1]];
    tmp += cnt[1][0][4] - cnt[1][0][p[2]];
    tmp += cnt[1][1][4] - cnt[1][1][p[3]];
    string a0, a1;
    a0 += di[p[0]];
    a0 += di[p[1]];
    a1 += di[p[2]];
    a1 += di[p[3]];
    for (int j = 2; j < m; ++j) {
      if (j % 2) {
        int cho1 =
            cnt[0][j][4] - cnt[0][j][p[1]] + cnt[1][j][4] - cnt[1][j][p[3]];
        int cho2 =
            cnt[0][j][4] - cnt[0][j][p[3]] + cnt[1][j][4] - cnt[1][j][p[1]];
        tmp += min(cho1, cho2);
        if (cho1 < cho2) {
          a0 += di[p[1]];
          a1 += di[p[3]];
        } else {
          a0 += di[p[3]];
          a1 += di[p[1]];
        }
      } else {
        int cho1 =
            cnt[0][j][4] - cnt[0][j][p[0]] + cnt[1][j][4] - cnt[1][j][p[2]];
        int cho2 =
            cnt[0][j][4] - cnt[0][j][p[2]] + cnt[1][j][4] - cnt[1][j][p[0]];
        tmp += min(cho1, cho2);
        if (cho1 < cho2) {
          a0 += di[p[0]];
          a1 += di[p[2]];
        } else {
          a0 += di[p[2]];
          a1 += di[p[0]];
        }
      }
    }
    if (step > tmp) {
      step = tmp;
      ans = (vector<string>){a0, a1};
    }
  } while (next_permutation(p.begin(), p.end()));
  for (int i = 2; i < n; ++i) {
    ans.push_back(ans[i % 2]);
  }
  return make_pair(step, ans);
}
int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  vector<string> a;
  for (int i = 0; i < n; ++i) {
    scanf("%s", s);
    string tmp = s;
    a.push_back(s);
  }
  vector<string> a0, a1, b, b1;
  int s0, s1;
  tie(s0, a0) = work(a);
  for (int i = 0; i < m; ++i) {
    string tmp;
    for (int j = 0; j < n; ++j) {
      tmp += a[j][i];
    }
    b.push_back(tmp);
  }
  tie(s1, b1) = work(b);
  for (int i = 0; i < n; ++i) {
    string tmp;
    for (int j = 0; j < m; ++j) {
      tmp += b1[j][i];
    }
    a1.push_back(tmp);
  }
  if (s1 < s0) {
    a0.swap(a1);
    swap(s1, s0);
  }
  for (string s : a0) {
    printf("%s\n", s.c_str());
  }
}
