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, ans;
vector<int> h[150010], t[150010], s[150010];
void cal1(int A, int B, int C, int D) {
  int res = 0;
  for (int i = 1; i <= n; i++) {
    int sum1 = 0, sum2 = 0;
    for (int j = 1; j <= m; j += 2) {
      if (i & 1) {
        sum1 += (s[i][j] != A) + (j < m && s[i][j + 1] != B);
        sum2 += (s[i][j] != B) + (j < m && s[i][j + 1] != A);
      } else {
        sum1 += (s[i][j] != C) + (j < m && s[i][j + 1] != D);
        sum2 += (s[i][j] != D) + (j < m && s[i][j + 1] != C);
      }
    }
    if (sum1 < sum2) {
      for (int j = 1; j <= m; j += 2) {
        if (i & 1)
          t[i][j] = A, t[i][j + 1] = B;
        else
          t[i][j] = C, t[i][j + 1] = D;
      }
      res += sum1;
    } else {
      for (int j = 1; j <= m; j += 2) {
        if (i & 1)
          t[i][j] = B, t[i][j + 1] = A;
        else
          t[i][j] = D, t[i][j + 1] = C;
      }
      res += sum2;
    }
  }
  if (res < ans) {
    for (int i = 1; i <= n; i++)
      for (int j = 1; j <= m; j++) h[i][j] = t[i][j];
    ans = res;
  }
}
void cal2(int A, int B, int C, int D) {
  int res = 0;
  for (int i = 1; i <= m; i++) {
    int sum1 = 0, sum2 = 0;
    for (int j = 1; j <= n; j += 2) {
      if (i & 1) {
        sum1 += (s[j][i] != A) + (j < n && s[j + 1][i] != B);
        sum2 += (s[j][i] != B) + (j < n && s[j + 1][i] != A);
      } else {
        sum1 += (s[j][i] != C) + (j < n && s[j + 1][i] != D);
        sum2 += (s[j][i] != D) + (j < n && s[j + 1][i] != C);
      }
    }
    if (sum1 < sum2) {
      for (int j = 1; j <= n; j += 2) {
        if (i & 1)
          t[j][i] = A, t[j + 1][i] = B;
        else
          t[j][i] = C, t[j + 1][i] = D;
      }
      res += sum1;
    } else {
      for (int j = 1; j <= n; j += 2) {
        if (i & 1)
          t[j][i] = B, t[j + 1][i] = A;
        else
          t[j][i] = D, t[j + 1][i] = C;
      }
      res += sum2;
    }
  }
  if (res < ans) {
    for (int i = 1; i <= n; i++)
      for (int j = 1; j <= m; j++) h[i][j] = t[i][j];
    ans = res;
  }
}
int get(char ch) {
  if (ch == 'A') return 0;
  if (ch == 'G') return 1;
  if (ch == 'T') return 2;
  return 3;
}
int C(int x) {
  if (x == 0) return 'A';
  if (x == 1) return 'G';
  if (x == 2) return 'T';
  return 'C';
}
int main() {
  char ch;
  int a, b;
  scanf("%d%d", &n, &m);
  ans = n * m;
  for (int i = 0; i <= n + 5; i++)
    for (int j = 0; j <= m + 5; j++)
      h[i].push_back(0), t[i].push_back(0), s[i].push_back(0);
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++) scanf(" %c", &ch), s[i][j] = get(ch);
  for (int i = 0; i <= 3; i++)
    for (int j = 0; j <= 3; j++) {
      if (i == j) continue;
      for (a = 0; a <= 3; a++)
        if (i != a && j != a) break;
      for (b = a + 1; b <= 3; b++)
        if (i != b && j != b) break;
      cal1(i, j, a, b);
      cal1(i, j, b, a);
      cal2(i, j, a, b);
      cal2(i, j, b, a);
    }
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) printf("%c", C(h[i][j]));
    printf("\n");
  }
  return 0;
}
