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;
int n, m;
vector<vector<int>> G;
vector<int> row_cost[4][4], col_cost[4][4];
int best_cost, type;
string s1, s2;
int getval(char c) {
  if (c == 'A') return 0;
  if (c == 'C') return 1;
  if (c == 'G') return 2;
  return 3;
}
char getsym(int v) {
  if (v == 0) return 'A';
  if (v == 1) return 'C';
  if (v == 2) return 'G';
  return 'T';
}
void compute_row_cost(int r, int a, int b) {
  for (int i = 0; i < m; i += 2)
    if (G[r][i] != a) row_cost[a][b][r]++;
  for (int i = 1; i < m; i += 2)
    if (G[r][i] != b) row_cost[a][b][r]++;
}
void compute_col_cost(int c, int a, int b) {
  for (int i = 0; i < n; i += 2)
    if (G[i][c] != a) col_cost[a][b][c]++;
  for (int i = 1; i < n; i += 2)
    if (G[i][c] != b) col_cost[a][b][c]++;
}
void check_best_row(int a, int b, int c, int d) {
  int cost = 0;
  string t1, t2;
  t1.resize(m);
  t2.resize(m);
  for (int i = 0; i < m; ++i) {
    if (i % 2 == 0) {
      cost += min(col_cost[a][b][i], col_cost[b][a][i]);
      if (col_cost[a][b][i] <= col_cost[b][a][i]) {
        t1[i] = getsym(a);
        t2[i] = getsym(b);
      } else {
        t1[i] = getsym(b);
        t2[i] = getsym(a);
      }
    } else {
      cost += min(col_cost[c][d][i], col_cost[d][c][i]);
      if (col_cost[c][d][i] <= col_cost[d][c][i]) {
        t1[i] = getsym(c);
        t2[i] = getsym(d);
      } else {
        t1[i] = getsym(d);
        t2[i] = getsym(c);
      }
    }
  }
  if (cost < best_cost) {
    s1 = t1;
    s2 = t2;
    best_cost = cost;
    type = 0;
  }
}
void check_best_col(int a, int b, int c, int d) {
  int cost = 0;
  string t1, t2;
  t1.resize(n);
  t2.resize(n);
  for (int i = 0; i < n; ++i) {
    if (i % 2 == 0) {
      cost += min(row_cost[a][b][i], row_cost[b][a][i]);
      if (row_cost[a][b][i] <= row_cost[b][a][i]) {
        t1[i] = getsym(a);
        t2[i] = getsym(b);
      } else {
        t1[i] = getsym(b);
        t2[i] = getsym(a);
      }
    } else {
      cost += min(row_cost[c][d][i], row_cost[d][c][i]);
      if (row_cost[c][d][i] <= row_cost[d][c][i]) {
        t1[i] = getsym(c);
        t2[i] = getsym(d);
      } else {
        t1[i] = getsym(d);
        t2[i] = getsym(c);
      }
    }
  }
  if (cost < best_cost) {
    s1 = t1;
    s2 = t2;
    best_cost = cost;
    type = 1;
  }
}
int main() {
  best_cost = 1e9;
  cin >> n >> m;
  G.resize(n);
  for (int i = 0; i < n; ++i) G[i].resize(m);
  for (int a = 0; a < 4; ++a)
    for (int b = 0; b < 4; ++b)
      if (a != b) row_cost[a][b].resize(n), col_cost[a][b].resize(m);
  for (int i = 0; i < n; ++i)
    for (int j = 0; j < m; ++j) {
      char c;
      cin >> c;
      G[i][j] = getval(c);
    }
  for (int i = 0; i < n; ++i)
    for (int a = 0; a < 4; ++a)
      for (int b = 0; b < 4; ++b)
        if (a != b) compute_row_cost(i, a, b);
  for (int i = 0; i < m; ++i)
    for (int a = 0; a < 4; ++a)
      for (int b = 0; b < 4; ++b)
        if (a != b) compute_col_cost(i, a, b);
  for (int a = 0; a < 4; ++a)
    for (int b = a + 1; b < 4; ++b) {
      int c, d;
      for (int i = 0; i < 4; ++i)
        if (i != a and i != b) {
          c = i;
          break;
        }
      for (int i = 0; i < 4; ++i)
        if (i != a and i != b and i != c) {
          d = i;
          break;
        }
      check_best_row(a, b, c, d);
      check_best_col(a, b, c, d);
    }
  if (type == 0) {
    for (int i = 0; i < n; ++i)
      if (i % 2 == 0)
        cout << s1 << "\n";
      else
        cout << s2 << "\n";
  } else {
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < m; ++j)
        if (j % 2 == 0)
          cout << s1[i];
        else
          cout << s2[i];
      cout << "\n";
    }
  }
}
