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;
const long long MOD = 1000000007;
const int INF = 0x3f3f3f3f;
const int MAXN = 300000 + 5;
const int MAXM = 400000 + 5;
int dr[MAXN][12];
int dc[MAXN][12];
int co[12][2] = {{1, 2}, {2, 1}, {1, 3}, {3, 1}, {1, 4}, {4, 1},
                 {2, 3}, {3, 2}, {2, 4}, {4, 2}, {3, 4}, {4, 3}};
int main() {
  ios_base::sync_with_stdio(0);
  int n, m;
  cin >> n >> m;
  int **a = new int *[n];
  int **b = new int *[n];
  for (int i = 0; i < n; i++) {
    a[i] = new int[m];
    b[i] = new int[m];
    string s;
    cin >> s;
    for (int j = 0; j < m; j++) {
      switch (s[j]) {
        case 'A':
          a[i][j] = 1;
          break;
        case 'G':
          a[i][j] = 2;
          break;
        case 'C':
          a[i][j] = 3;
          break;
        case 'T':
          a[i][j] = 4;
          break;
      }
    }
  }
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      for (int k = 0; k < 12; k++) {
        if (a[i][j] != co[k][j & 1]) {
          dr[i][k]++;
        }
        if (a[i][j] != co[k][i & 1]) {
          dc[j][k]++;
        }
      }
    }
  }
  int ans = INF;
  int ansrc = 0;
  int ansco = 0;
  for (int k = 0; k < 12; k++) {
    int cnt = 0;
    for (int i = 0; i < n; i++) {
      if (i & 1) {
        cnt += min(dr[i][11 - k], dr[i][(11 - k) ^ 1]);
      } else {
        cnt += min(dr[i][k], dr[i][k ^ 1]);
      }
    }
    if (cnt < ans) {
      ans = cnt;
      ansrc = 0;
      ansco = k;
    }
    cnt = 0;
    for (int j = 0; j < m; j++) {
      if (j & 1) {
        cnt += min(dc[j][11 - k], dc[j][(11 - k) ^ 1]);
      } else {
        cnt += min(dc[j][k], dc[j][k ^ 1]);
      }
    }
    if (cnt < ans) {
      ans = cnt;
      ansrc = 1;
      ansco = k;
    }
  }
  int k = ansco;
  if (ansrc == 0) {
    for (int i = 0; i < n; i++) {
      int _k;
      if (i & 1) {
        _k = (11 - k) ^ (dr[i][11 - k] >= dr[i][(11 - k) ^ 1]);
      } else {
        _k = k ^ (dr[i][k] >= dr[i][k ^ 1]);
      }
      for (int j = 0; j < m; j++) {
        b[i][j] = co[_k][j & 1];
      }
    }
  } else {
    for (int j = 0; j < m; j++) {
      int _k;
      if (j & 1) {
        _k = (11 - k) ^ (dc[j][11 - k] >= dc[j][(11 - k) ^ 1]);
      } else {
        _k = k ^ (dc[j][k] >= dc[j][k ^ 1]);
      }
      for (int i = 0; i < n; i++) {
        b[i][j] = co[_k][i & 1];
      }
    }
  }
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      switch (b[i][j]) {
        case 1:
          putchar('A');
          break;
        case 2:
          putchar('G');
          break;
        case 3:
          putchar('C');
          break;
        case 4:
          putchar('T');
          break;
      }
    }
    putchar('\n');
  }
  return 0;
}
