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, ord1[300005][6], cnt1[300005], ord2[300005][6], cnt2[300005];
char str[6][2] = {{'A', 'C'}, {'A', 'G'}, {'A', 'T'},
                  {'C', 'G'}, {'C', 'T'}, {'G', 'T'}};
string s[300005], pri[300005];
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 0; i < n; i++) {
    cin >> s[i];
  }
  memset(cnt1, 0, sizeof(cnt1));
  memset(cnt2, 0, sizeof(cnt2));
  for (int i = 0; i < n; i++) {
    for (int k = 0; k < 6; k++) {
      int now1 = 0, now2 = 0;
      for (int j = 0; j < m; j++) {
        now1 += (s[i][j] != str[(i & 1) ? 5 - k : k][j & 1]);
        now2 += (s[i][j] != str[(i & 1) ? 5 - k : k][(j & 1) ^ 1]);
      }
      cnt1[k] += min(now1, now2);
      ord1[i][k] = now1 < now2 ? 0 : 1;
    }
  }
  for (int j = 0; j < m; j++) {
    for (int k = 0; k < 6; k++) {
      int now1 = 0, now2 = 0;
      for (int i = 0; i < n; i++) {
        now1 += (s[i][j] != str[(j & 1) ? 5 - k : k][i & 1]);
        now2 += (s[i][j] != str[(j & 1) ? 5 - k : k][(i & 1) ^ 1]);
      }
      cnt2[k] += min(now1, now2);
      ord2[j][k] = now1 < now2 ? 0 : 1;
    }
  }
  int minn = 1e9, ans, ansk;
  for (int k = 0; k < 6; k++) {
    if (cnt1[k] < minn) minn = cnt1[k], ans = 0, ansk = k;
  }
  for (int k = 0; k < 6; k++) {
    if (cnt2[k] < minn) minn = cnt2[k], ans = 1, ansk = k;
  }
  if (ans == 0) {
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        pri[i] += str[(i & 1) ? 5 - ansk : ansk][(j & 1) ^ ord1[i][ansk]];
      }
    }
  }
  if (ans == 1) {
    for (int j = 0; j < m; j++) {
      for (int i = 0; i < n; i++) {
        pri[i] += str[(j & 1) ? 5 - ansk : ansk][(i & 1) ^ ord2[j][ansk]];
      }
    }
  }
  for (int i = 0; i < n; i++) cout << pri[i] << endl;
  return 0;
}
