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;
string str[200000 + 1];
int N, M;
char c[2][2];
char alpha[4] = {'A', 'C', 'G', 'T'};
int t[4] = {0, 1, 2, 3};
string ans[200000 + 1], now[200000 + 1];
int acnt = -1, ncnt = 0, cnt1 = 0, cnt2;
int main() {
  scanf("%d%d", &N, &M);
  for (int i = 0; i < N; i++) {
    cin >> str[i];
    ans[i] = now[i] = str[i];
  }
  for (int k = 1; k <= 24; k++) {
    for (int ii = 0; ii < 2; ii++) {
      for (int jj = 0; jj < 2; jj++) {
        c[ii][jj] = alpha[t[ii * 2 + jj]];
      }
    }
    ncnt = 0;
    for (int i = 0; i < N; i++) {
      cnt1 = 0;
      cnt2 = 0;
      for (int j = 0; j < M; j++) {
        if (str[i][j] == c[i % 2][j % 2]) {
          cnt1++;
        }
        if (str[i][j] == c[i % 2][(j + 1) % 2]) {
          cnt2++;
        }
      }
      if (cnt1 > cnt2) {
        for (int j = 0; j < M; j++) {
          now[i][j] = c[i % 2][j % 2];
        }
        ncnt += cnt1;
      } else {
        for (int j = 0; j < M; j++) {
          now[i][j] = c[i % 2][(j + 1) % 2];
        }
        ncnt += cnt2;
      }
    }
    if (ncnt > acnt) {
      acnt = ncnt;
      for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
          ans[i][j] = now[i][j];
        }
      }
    }
    ncnt = 0;
    for (int j = 0; j < M; j++) {
      cnt1 = 0;
      cnt2 = 0;
      for (int i = 0; i < N; i++) {
        if (str[i][j] == c[i % 2][j % 2]) {
          cnt1++;
        }
        if (str[i][j] == c[(i + 1) % 2][j % 2]) {
          cnt2++;
        }
      }
      if (cnt1 > cnt2) {
        for (int i = 0; i < N; i++) {
          now[i][j] = c[i % 2][j % 2];
        }
        ncnt += cnt1;
      } else {
        for (int i = 0; i < N; i++) {
          now[i][j] = c[(i + 1) % 2][j % 2];
        }
        ncnt += cnt2;
      }
    }
    if (ncnt > acnt) {
      acnt = ncnt;
      for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
          ans[i][j] = now[i][j];
        }
      }
    }
    next_permutation(t, t + 4);
  }
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < M; j++) {
      printf("%c", ans[i][j]);
    }
    printf("\n");
  }
}
