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> char2num = {{'A', 0}, {'C', 1}, {'G', 2}, {'T', 3}};
string num2char = "ACGT";
int a[300020];
char s[300020];
int temp_a[300020], best_a[300020];
int best_ans;
int get(int row, int col, int tran) {
  if (!tran) return row * m + col;
  return col * m + row;
}
void check(int i, int j, int tran) {
  int kk = -1, pp = -1;
  for (int temp = 0; temp < 4; temp++) {
    if (temp != i && temp != j) {
      if (kk < 0)
        kk = temp;
      else
        pp = temp;
    }
  }
  int num_row = tran ? m : n, num_col = m + n - num_row;
  int gain = 0;
  for (int row = 0; row < num_row; row++) {
    int k = i, p = j;
    if (row & 1) k = kk, p = pp;
    int kp_gain = 0, pk_gain = 0;
    for (int col = 0; col < num_col; col++) {
      int val = a[get(row, col, tran)];
      if (col & 1) {
        if (val == p) kp_gain++;
        if (val == k) pk_gain++;
      } else {
        if (val == k) kp_gain++;
        if (val == p) pk_gain++;
      }
    }
    gain += max(kp_gain, pk_gain);
    for (int col = 0; col < num_col; col++) {
      int loc = get(row, col, tran);
      if (col & 1) {
        if (kp_gain > pk_gain)
          temp_a[loc] = p;
        else
          temp_a[loc] = k;
      } else {
        if (kp_gain > pk_gain)
          temp_a[loc] = k;
        else
          temp_a[loc] = p;
      }
    }
  }
  if (gain > best_ans) {
    best_ans = gain;
    for (int it = 0; it < n * m; it++) best_a[it] = temp_a[it];
  }
}
int main() {
  while (scanf("%d%d", &n, &m) != EOF) {
    for (int i = 0; i < n; i++) {
      scanf("%s", s);
      for (int j = 0; j < m; j++) a[i * m + j] = char2num[s[j]];
    }
    best_ans = -1;
    for (int i = 0; i < 4; i++) {
      for (int j = i + 1; j < 4; j++) {
        for (int tran = 0; tran < 2; tran++) {
          check(i, j, tran);
        }
      }
    }
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) putchar(num2char[best_a[i * m + j]]);
      puts("");
    }
  }
}
