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>
std::mt19937 rng(
    (int)std::chrono::steady_clock::now().time_since_epoch().count());
int n, m;
std::string mat[300300], wtf[300300];
std::string wut[300300];
std::string dna = "ACGT";
int count = 0;
int ans = (int)1e9;
void brute(int i, int j, int cost) {
  if (cost >= ans) return;
  if (n == i) {
    ans = cost;
    for (int k = 0; k < n; k++) {
      wut[k] = wtf[k];
    }
    return;
  }
  if (m == j) {
    brute(i + 1, 0, cost);
    return;
  }
  for (auto c : dna) {
    if (i && wtf[i - 1][j] == c) continue;
    if (j && wtf[i][j - 1] == c) continue;
    if (i && j + 1 < m && wtf[i - 1][j + 1] == c) continue;
    if (i && j && wtf[i - 1][j - 1] == c) continue;
    wtf[i][j] = c;
    brute(i, j + 1, cost + (c != mat[i][j] ? 1 : 0));
  }
}
int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(NULL);
  std::cin >> n >> m;
  if (false) {
    for (int i = 0; i < n; i++) {
      mat[i] = wtf[i] = std::string(m, '#');
    }
    brute(0, 0, 0);
    std::cout << ans << '\n';
    for (int i = 0; i < n; i++) {
      std::cout << wut[i] << '\n';
    }
  } else {
    int p[] = {0, 1, 2, 3};
    for (int i = 0; i < n; i++) {
      mat[i] = wtf[i] = std::string(m, '#');
      std::cin >> mat[i];
    }
    do {
      if (p[0] > p[1] || p[2] > p[3]) continue;
      {
        int cost = n * m;
        for (int j = 0; j < m; j++) {
          int a1, a2;
          if (j % 2 == 0) {
            a1 = p[0], a2 = p[1];
          } else {
            a1 = p[2], a2 = p[3];
          }
          int cost1 = 0;
          int cost2 = 0;
          for (int i = 0; i < n; i++) {
            if (mat[i][j] == dna[a1]) {
              cost1++;
            } else if (mat[i][j] == dna[a2]) {
              cost2++;
            }
            std::swap(a1, a2);
          }
          if (j % 2 == 0) {
            a1 = p[0], a2 = p[1];
          } else {
            a1 = p[2], a2 = p[3];
          }
          if (cost2 > cost1) {
            std::swap(a1, a2);
            std::swap(cost2, cost1);
          }
          cost -= cost1;
          for (int i = 0; i < n; i++) {
            wtf[i][j] = dna[a1];
            std::swap(a1, a2);
          }
        }
        if (cost < ans) {
          ans = cost;
          for (int i = 0; i < n; i++) {
            wut[i] = wtf[i];
          }
        }
      }
      {
        int cost = n * m;
        for (int i = 0; i < n; i++) {
          int a1, a2;
          if (i % 2 == 0) {
            a1 = p[0], a2 = p[1];
          } else {
            a1 = p[2], a2 = p[3];
          }
          int cost1 = 0;
          int cost2 = 0;
          for (int j = 0; j < m; j++) {
            if (mat[i][j] == dna[a1]) {
              cost1++;
            } else if (mat[i][j] == dna[a2]) {
              cost2++;
            }
            std::swap(a1, a2);
          }
          if (i % 2 == 0) {
            a1 = p[0], a2 = p[1];
          } else {
            a1 = p[2], a2 = p[3];
          }
          if (cost2 > cost1) {
            std::swap(a1, a2);
            std::swap(cost2, cost1);
          }
          cost -= cost1;
          for (int j = 0; j < m; j++) {
            wtf[i][j] = dna[a1];
            std::swap(a1, a2);
          }
        }
        if (cost < ans) {
          ans = cost;
          for (int i = 0; i < n; i++) {
            wut[i] = wtf[i];
          }
        }
      }
    } while (std::next_permutation(p, p + 4));
    for (int i = 0; i < n; i++) {
      std::cout << wut[i] << '\n';
    }
  }
}
