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, arr[1000000 + 5], cek[1000000 + 5], res[1000000 + 5];
char temp;
inline int conv(char x) {
  if (x == 'A')
    return 0;
  else if (x == 'G')
    return 1;
  else if (x == 'C')
    return 2;
  else
    return 3;
}
inline char rconv(int x) {
  if (x == 0)
    return 'A';
  else if (x == 1)
    return 'G';
  else if (x == 2)
    return 'C';
  else
    return 'T';
}
inline bool eval(int a, int b, int c, int d) {
  int x[4] = {a, b, c, d};
  sort(x, x + 4);
  for (int i = 0; i < 3; i++) {
    if (x[i] == x[i + 1]) return false;
  }
  return true;
}
void printBoard() {
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      printf("%c", rconv(res[i * m + j]));
    }
    printf("\n");
  }
}
int main() {
  scanf("%d %d", &n, &m);
  for (int i = 0; i < n; i++) {
    getchar();
    for (int j = 0; j < m; j++) {
      scanf("%c", &temp);
      arr[i * m + j] = conv(temp);
    }
  }
  int xam = n * m + 5;
  for (int i = 0; i < (1 << 8); i++) {
    int tempx = i;
    int a[4];
    for (int j = 0; j < 4; j++) {
      a[j] = tempx % 4;
      tempx /= 4;
    }
    if (!eval(a[0], a[1], a[2], a[3])) continue;
    int val = 0;
    for (int j = 0; j < n; j++) {
      for (int k = 0; k < m; k++) {
        cek[j * m + k] = a[(j % 2) * 2 + k % 2];
        if (cek[j * m + k] != arr[j * m + k]) val++;
      }
    }
    bool flag = true;
    for (int j = 0; j < n - 1 && flag; j++) {
      for (int k = 0; k < m - 1 && flag; k++) {
        flag &= eval(cek[j * m + k], cek[j * m + (k + 1)], cek[(j + 1) * m + k],
                     cek[(j + 1) * m + (k + 1)]);
      }
    }
    if (flag and xam > val) {
      xam = val;
      for (int j = 0; j < n; j++) {
        for (int k = 0; k < m; k++) {
          res[j * m + k] = cek[j * m + k];
        }
      }
    }
    val = 0;
    for (int j = 0; j < n; j++) {
      int v1 = 0;
      int v2 = 0;
      for (int k = 0; k < m; k++) {
        if (a[((k % 2) * 2 + j) % 4] == arr[j * m + k])
          v1++;
        else if (a[(((k + 1) % 2) * 2 + j) % 4] == arr[j * m + k])
          v2++;
      }
      if (v1 > v2) {
        for (int k = 0; k < m; k++) {
          cek[j * m + k] = a[((k % 2) * 2 + j) % 4];
          if (cek[j * m + k] != arr[j * m + k]) val++;
        }
      } else {
        for (int k = 0; k < m; k++) {
          cek[j * m + k] = a[(((k + 1) % 2) * 2 + j) % 4];
          if (cek[j * m + k] != arr[j * m + k]) val++;
        }
      }
    }
    flag = true;
    for (int j = 0; j < n - 1 && flag; j++) {
      for (int k = 0; k < m - 1 && flag; k++) {
        flag &= eval(cek[j * m + k], cek[j * m + (k + 1)], cek[(j + 1) * m + k],
                     cek[(j + 1) * m + (k + 1)]);
      }
    }
    if (flag and xam > val) {
      xam = val;
      for (int j = 0; j < n; j++) {
        for (int k = 0; k < m; k++) {
          res[j * m + k] = cek[j * m + k];
        }
      }
    }
    val = 0;
    for (int k = 0; k < m; k++) {
      int v1 = 0;
      int v2 = 0;
      for (int j = 0; j < n; j++) {
        if (a[((j % 2) * 2 + k) % 4] == arr[j * m + k])
          v1++;
        else if (a[(((j + 1) % 2) * 2 + k) % 4] == arr[j * m + k])
          v2++;
      }
      if (v1 > v2) {
        for (int j = 0; j < n; j++) {
          cek[j * m + k] = a[((j % 2) * 2 + k) % 4];
          if (cek[j * m + k] != arr[j * m + k]) val++;
        }
      } else {
        for (int j = 0; j < n; j++) {
          cek[j * m + k] = a[(((j + 1) % 2) * 2 + k) % 4];
          if (cek[j * m + k] != arr[j * m + k]) val++;
        }
      }
    }
    flag = true;
    for (int j = 0; j < n - 1 && flag; j++) {
      for (int k = 0; k < m - 1 && flag; k++) {
        flag &= eval(cek[j * m + k], cek[j * m + (k + 1)], cek[(j + 1) * m + k],
                     cek[(j + 1) * m + (k + 1)]);
      }
    }
    if (flag and xam > val) {
      xam = val;
      for (int j = 0; j < n; j++) {
        for (int k = 0; k < m; k++) {
          res[j * m + k] = cek[j * m + k];
        }
      }
    }
  }
  printBoard();
}
