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 AXN = 1e6;
int n, k;
vector<int> a[AXN];
int cur[20], ans_col[20], ans_row[20], pair_ans;
pair<int, int> col[20], row[20];
int calc_col(int q, int x, int y) {
  int ans = 0;
  for (int i = 0; i < n; i++)
    if (i % 2 == 0)
      ans += (a[i][q] != x);
    else
      ans += (a[i][q] != y);
  return ans;
}
int calc_row(int q, int x, int y) {
  int ans = 0;
  for (int i = 0; i < k; i++)
    if (i % 2 == 0)
      ans += (a[q][i] != x);
    else
      ans += (a[q][i] != y);
  return ans;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> k;
  for (int i = 0; i < n; i++) {
    for (int q = 0; q < k; q++) {
      char c;
      cin >> c;
      if (c == 'A') a[i].push_back(0);
      if (c == 'C') a[i].push_back(1);
      if (c == 'G') a[i].push_back(2);
      if (c == 'T') a[i].push_back(3);
    }
  }
  int ans = 1e9;
  vector<pair<int, int> > col[k];
  for (int q = 0; q < k; q++) {
    col[q].resize(16);
    for (int i = 0; i < 4; i++)
      for (int w = i + 1; w < 4; w++) {
        cur[(1 << i) + (1 << w)] = calc_col(q, i, w);
        if (q % 2 == 0)
          col[q][(1 << i) + (1 << w)] = make_pair(i, w);
        else
          col[q][15 ^ ((1 << i) + (1 << w))] = make_pair(i, w);
      }
    for (int i = 0; i < 4; i++)
      for (int w = 0; w < i; w++) {
        int k = calc_col(q, i, w);
        if (cur[(1 << i) + (1 << w)] > k) {
          cur[(1 << i) + (1 << w)] = k;
          if (q % 2 == 0)
            col[q][(1 << i) + (1 << w)] = make_pair(i, w);
          else
            col[q][15 ^ ((1 << i) + (1 << w))] = make_pair(i, w);
        }
      }
    for (int i = 0; i < 4; i++)
      for (int w = 0; w < i; w++)
        if (q % 2)
          ans_col[15 ^ ((1 << i) + (1 << w))] += cur[(1 << i) + (1 << w)];
        else
          ans_col[(1 << i) + (1 << w)] += cur[(1 << i) + (1 << w)];
  }
  for (int i = 0; i < 4; i++)
    for (int w = 0; w < i; w++)
      if (ans > ans_col[(1 << i) + (1 << w)]) {
        ans = ans_col[(1 << i) + (1 << w)];
        pair_ans = (1 << i) + (1 << w);
      }
  vector<pair<int, int> > row[n];
  for (int q = 0; q < n; q++) {
    row[q].resize(16);
    for (int i = 0; i < 4; i++)
      for (int w = i + 1; w < 4; w++) {
        cur[(1 << i) + (1 << w)] = calc_row(q, i, w);
        if (q % 2 == 0)
          row[q][(1 << i) + (1 << w)] = make_pair(i, w);
        else
          row[q][15 ^ ((1 << i) + (1 << w))] = make_pair(i, w);
      }
    for (int i = 0; i < 4; i++)
      for (int w = 0; w < i; w++) {
        int k = calc_row(q, i, w);
        if (cur[(1 << i) + (1 << w)] > k) {
          cur[(1 << i) + (1 << w)] = k;
          if (q % 2 == 0)
            row[q][(1 << i) + (1 << w)] = make_pair(i, w);
          else
            row[q][15 ^ ((1 << i) + (1 << w))] = make_pair(i, w);
        }
      }
    for (int i = 0; i < 4; i++)
      for (int w = 0; w < i; w++)
        if (q % 2)
          ans_row[15 ^ ((1 << i) + (1 << w))] += cur[(1 << i) + (1 << w)];
        else
          ans_row[(1 << i) + (1 << w)] += cur[(1 << i) + (1 << w)];
  }
  bool flag = false;
  for (int i = 0; i < 4; i++)
    for (int w = 0; w < i; w++)
      if (ans > ans_row[(1 << i) + (1 << w)]) {
        flag = true;
        ans = ans_row[(1 << i) + (1 << w)];
        pair_ans = (1 << i) + (1 << w);
      }
  if (!flag) {
    for (int i = 0; i < n; i++)
      for (int q = 0; q < k; q++)
        if (i % 2 == 0)
          a[i][q] = col[q][pair_ans].first;
        else
          a[i][q] = col[q][pair_ans].second;
  } else {
    for (int i = 0; i < n; i++)
      for (int q = 0; q < k; q++)
        if (q % 2 == 0)
          a[i][q] = row[i][pair_ans].first;
        else
          a[i][q] = row[i][pair_ans].second;
  }
  for (int i = 0; i < n; i++) {
    for (int q = 0; q < k; q++) {
      if (a[i][q] == 0) cout << 'A';
      if (a[i][q] == 1) cout << 'C';
      if (a[i][q] == 2) cout << 'G';
      if (a[i][q] == 3) cout << 'T';
    }
    cout << "\n";
  }
}
