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, nn[300000][2][4], mm[300000][2][4], ans, sign, a1, a2, pp[300000];
char s[300000];
int trans(char c) {
  if (c == 'A')
    return 0;
  else if (c == 'G')
    return 1;
  else if (c == 'C')
    return 2;
  else
    return 3;
}
char tran2(int a) {
  if (a == 0)
    return 'A';
  else if (a == 1)
    return 'G';
  else if (a == 2)
    return 'C';
  else
    return 'T';
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) {
    scanf("%s", s + 1);
    for (int j = 1; j <= m; j++) {
      nn[i][j % 2][trans(s[j])]++;
      mm[j][i % 2][trans(s[j])]++;
    }
  }
  for (int i = 0; i <= 3; i++) {
    for (int j = i + 1; j <= 3; j++) {
      if (i == j) continue;
      int k, l, sum = 0;
      for (k = 0; k <= 3; k++) {
        if (k != i && k != j) {
          break;
        }
      }
      for (l = k + 1; l <= 3; l++) {
        if (l != i && l != j) {
          break;
        }
      }
      for (int q = 1; q <= n; q++) {
        if (q % 2)
          sum += max(nn[q][0][i] + nn[q][1][j], nn[q][1][i] + nn[q][0][j]);
        else
          sum += max(nn[q][0][k] + nn[q][1][l], nn[q][1][k] + nn[q][0][l]);
      }
      if (sum > ans) {
        ans = sum;
        sign = 0;
        a1 = i;
        a2 = j;
      }
    }
  }
  for (int i = 0; i <= 3; i++) {
    for (int j = i + 1; j <= 3; j++) {
      if (i == j) continue;
      int k, l, sum = 0;
      for (k = 0; k <= 3; k++) {
        if (k != i && k != j) {
          break;
        }
      }
      for (l = k + 1; l <= 3; l++) {
        if (l != i && l != j) {
          break;
        }
      }
      for (int q = 1; q <= m; q++) {
        if (q % 2)
          sum += max(mm[q][0][i] + mm[q][1][j], mm[q][1][i] + mm[q][0][j]);
        else
          sum += max(mm[q][0][k] + mm[q][1][l], mm[q][1][k] + mm[q][0][l]);
      }
      if (sum > ans) {
        ans = sum;
        sign = 1;
        a1 = i;
        a2 = j;
      }
    }
  }
  if (sign == 0) {
    int i = a1, j = a2, k, l;
    for (k = 0; k <= 3; k++) {
      if (k != i && k != j) {
        break;
      }
    }
    for (l = k + 1; l <= 3; l++) {
      if (l != i && l != j) {
        break;
      }
    }
    for (int q = 1; q <= n; q++) {
      if (q % 2) {
        if (nn[q][0][i] + nn[q][1][j] > nn[q][1][i] + nn[q][0][j])
          a1 = j, a2 = i;
        else
          a1 = i, a2 = j;
      } else {
        if (nn[q][0][k] + nn[q][1][l] > nn[q][1][k] + nn[q][0][l])
          a1 = l, a2 = k;
        else
          a1 = k, a2 = l;
      }
      for (int p = 1; p <= m; p++) {
        if (p % 2) {
          printf("%c", tran2(a1));
        } else
          printf("%c", tran2(a2));
      }
      printf("\n");
    }
  } else {
    int i = a1, j = a2, k, l;
    for (k = 0; k <= 3; k++) {
      if (k != i && k != j) {
        break;
      }
    }
    for (l = k + 1; l <= 3; l++) {
      if (l != i && l != j) {
        break;
      }
    }
    int rrr[4];
    rrr[i] = j;
    rrr[j] = i;
    rrr[k] = l;
    rrr[l] = k;
    for (int p = 1; p <= m; p++) {
      if (p % 2) {
        if (mm[p][0][i] + mm[p][1][j] > mm[p][1][i] + mm[p][0][j])
          pp[p] = j;
        else
          pp[p] = i;
      } else {
        if (mm[p][0][k] + mm[p][1][l] > mm[p][1][k] + mm[p][0][l])
          pp[p] = l;
        else
          pp[p] = k;
      }
    }
    for (int p = 1; p <= n; p++) {
      if (p % 2)
        for (int q = 1; q <= m; q++) printf("%c", tran2(pp[q]));
      else
        for (int q = 1; q <= m; q++) printf("%c", tran2(rrr[pp[q]]));
      printf("\n");
    }
  }
  return 0;
}
