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<char> A[300009], B[300009];
char S[5] = "ACGT";
void ga(char a, char b, char c, char d) {
  int cnt = 0;
  vector<bool> chk(N, 0);
  for (int i = 0; i < N; i++) {
    int s1 = 0, s2 = 0;
    for (int j = 0; j < M; j++) {
      if (i % 2) {
        if (A[i][j] != c && A[i][j] != d && (A[i][j] == a) ^ (j % 2)) ++s1;
        if (A[i][j] != c && A[i][j] != d && (A[i][j] == b) ^ (j % 2)) ++s2;
      } else {
        if (A[i][j] != a && A[i][j] != b && (A[i][j] == c) ^ (j % 2)) ++s1;
        if (A[i][j] != a && A[i][j] != b && (A[i][j] == d) ^ (j % 2)) ++s2;
      }
    }
    cnt += max(s1, s2);
    if (s1 > s2) chk[i] = 1;
  }
  if (ans < cnt) {
    ans = cnt;
    for (int i = 0; i < N; i++) {
      if (chk[i]) {
        for (int j = 0; j < M; j++) {
          if (i % 2)
            B[i][j] = j % 2 ? b : a;
          else
            B[i][j] = j % 2 ? d : c;
        }
      } else {
        for (int j = 0; j < M; j++) {
          if (i % 2)
            B[i][j] = j % 2 ? a : b;
          else
            B[i][j] = j % 2 ? c : d;
        }
      }
    }
  }
}
void se(char a, char b, char c, char d) {
  int cnt = 0;
  vector<bool> chk(M, 0);
  for (int i = 0; i < M; i++) {
    int s1 = 0, s2 = 0;
    for (int j = 0; j < N; j++) {
      if (i % 2) {
        if (A[j][i] != c && A[j][i] != d && (A[j][i] == a) ^ (j % 2)) ++s1;
        if (A[j][i] != c && A[j][i] != d && (A[j][i] == b) ^ (j % 2)) ++s2;
      } else {
        if (A[j][i] != a && A[j][i] != b && (A[j][i] == c) ^ (j % 2)) ++s1;
        if (A[j][i] != a && A[j][i] != b && (A[j][i] == d) ^ (j % 2)) ++s2;
      }
    }
    cnt += max(s1, s2);
    if (s1 > s2) chk[i] = 1;
  }
  if (ans < cnt) {
    ans = cnt;
    for (int i = 0; i < M; i++) {
      if (chk[i]) {
        for (int j = 0; j < N; j++) {
          if (i % 2)
            B[j][i] = j % 2 ? b : a;
          else
            B[j][i] = j % 2 ? d : c;
        }
      } else {
        for (int j = 0; j < N; j++) {
          if (i % 2)
            B[j][i] = j % 2 ? a : b;
          else
            B[j][i] = j % 2 ? c : d;
        }
      }
    }
  }
}
int main() {
  scanf("%d%d", &N, &M);
  for (int i = 0; i < N; i++) {
    A[i].resize(M);
    B[i].resize(M);
    for (int j = 0; j < M; j++) {
      scanf(" %c", &A[i][j]);
    }
  }
  for (int a = 0; a < 4; a++) {
    for (int b = 0; b < 4; b++) {
      for (int c = 0; c < 4; c++) {
        for (int d = 0; d < 4; d++) {
          set<int> st;
          st.insert(a);
          st.insert(b);
          st.insert(c);
          st.insert(d);
          if ((int)st.size() == 4) {
            ga(S[a], S[b], S[c], S[d]);
            se(S[a], S[b], S[c], S[d]);
          }
        }
      }
    }
  }
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < M; j++) {
      printf("%c", B[i][j]);
    }
    puts("");
  }
  return 0;
}
