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;
map<char, int> char_idx;
vector<char> idx_to_char;
const int INF = 1e8;
int main() {
  ios_base::sync_with_stdio(false);
  char_idx['A'] = 0;
  char_idx['C'] = 1;
  char_idx['G'] = 2;
  char_idx['T'] = 3;
  idx_to_char = {'A', 'C', 'G', 'T'};
  cin >> n >> m;
  vector<vector<int>> table;
  table.assign(n, vector<int>(m));
  for (int i = 0; i != n; ++i) {
    for (int j = 0; j != m; ++j) {
      char c;
      cin >> c;
      table[i][j] = char_idx[c];
    }
  }
  int L = char_idx.size();
  vector<vector<vector<int>>> row_cost;
  vector<vector<vector<int>>> column_cost;
  row_cost.assign(n, vector<vector<int>>(L, vector<int>(L)));
  for (int i = 0; i != n; ++i) {
    for (int c1 = 0; c1 != L; ++c1) {
      for (int c2 = 0; c2 != L; ++c2) {
        if (c1 == c2)
          row_cost[i][c1][c2] = INF;
        else {
          int c[2] = {c1, c2};
          row_cost[i][c1][c2] = 0;
          for (int j = 0; j != m; ++j)
            row_cost[i][c1][c2] += table[i][j] != c[j % 2];
        }
      }
    }
  }
  column_cost.assign(m, vector<vector<int>>(L, vector<int>(L)));
  for (int j = 0; j != m; ++j) {
    for (int c1 = 0; c1 != L; ++c1) {
      for (int c2 = 0; c2 != L; ++c2) {
        if (c1 == c2)
          column_cost[j][c1][c2] = INF;
        else {
          int c[2] = {c1, c2};
          column_cost[j][c1][c2] = 0;
          for (int i = 0; i != n; ++i)
            column_cost[j][c1][c2] += table[i][j] != c[i % 2];
        }
      }
    }
  }
  int best_cost = INF;
  vector<int> best_solution = {0, 0};
  bool is_best_rowwise;
  for (int c1 = 0; c1 != L; ++c1) {
    for (int c2 = c1 + 1; c2 != L; ++c2) {
      int c3 = (c1 + 1) % 4;
      if (c2 == c3) c3 = (c3 + 1) % 4;
      int c4 = (c1 + 3) % 4;
      if (c2 == c4) c4 = (c4 + 3) % 4;
      int cost = 0;
      for (int i = 0; i != n; ++i) {
        int cx = (i % 2) == 0 ? c1 : c3;
        int cy = (i % 2) == 0 ? c2 : c4;
        cost += min(row_cost[i][cx][cy], row_cost[i][cy][cx]);
      }
      if (cost < best_cost) {
        best_cost = cost;
        best_solution = {c1, c2, c3, c4};
        is_best_rowwise = true;
      }
    }
  }
  for (int c1 = 0; c1 != L; ++c1) {
    for (int c2 = c1 + 1; c2 != L; ++c2) {
      int c3 = (c1 + 1) % 4;
      if (c2 == c3) c3 = (c3 + 1) % 4;
      int c4 = (c1 + 3) % 4;
      if (c2 == c4) c4 = (c4 + 3) % 4;
      int cost = 0;
      for (int j = 0; j != m; ++j) {
        int cx = (j % 2) == 0 ? c1 : c3;
        int cy = (j % 2) == 0 ? c2 : c4;
        cost += min(column_cost[j][cx][cy], column_cost[j][cy][cx]);
      }
      if (cost < best_cost) {
        best_cost = cost;
        best_solution = {c1, c2, c3, c4};
        is_best_rowwise = false;
      }
    }
  }
  vector<vector<char>> output_table(n, vector<char>(m));
  vector<char> r;
  for (auto x : best_solution) r.push_back(idx_to_char[x]);
  vector<int> c(best_solution.begin(), best_solution.end());
  if (is_best_rowwise) {
    for (int i = 0; i != n; ++i) {
      int cx = c[0 + 2 * (i % 2)];
      int cy = c[1 + 2 * (i % 2)];
      vector<char> out;
      if (row_cost[i][cy][cx] < row_cost[i][cx][cy])
        out = {idx_to_char[cy], idx_to_char[cx]};
      else
        out = {idx_to_char[cx], idx_to_char[cy]};
      for (int j = 0; j != m; ++j) output_table[i][j] = out[j % 2];
    }
  } else {
    for (int j = 0; j != m; ++j) {
      int cx = c[0 + 2 * (j % 2)];
      int cy = c[1 + 2 * (j % 2)];
      vector<char> out;
      if (column_cost[j][cy][cx] < column_cost[j][cx][cy])
        out = {idx_to_char[cy], idx_to_char[cx]};
      else
        out = {idx_to_char[cx], idx_to_char[cy]};
      for (int i = 0; i != n; ++i) output_table[i][j] = out[i % 2];
    }
  }
  for (auto& row : output_table) {
    for (auto& c : row) {
      cout << c;
    }
    cout << "\n";
  }
}
