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;
long long mult(long long a, long long b, long long p = 1000000007) {
  long long ans = ((a % p) * (b % p)) % p;
  return (ans + p) % p;
}
long long add(long long a, long long b, long long p = 1000000007) {
  long long ans = (a % p + b % p) % p;
  return (ans + p) % p;
}
long long fpow(long long n, long long k, long long p = 1000000007) {
  long long r = 1;
  for (; k; k >>= 1) {
    if (k & 1) r = r * n % p;
    n = n * n % p;
  }
  return r;
}
long long inv(long long a, long long p = 1000000007) {
  return fpow(a, p - 2, p);
}
const int N = 3e5 + 10, inf = 1e9;
vector<string> inp(N);
vector<string> transposeinp(N);
vector<string> place1(N);
vector<string> place2(N);
void transpose(int n, int m) {
  for (int i = 0; i < m; i++) transposeinp[i].resize(n);
  for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++) transposeinp[j][i] = inp[i][j];
}
int fillandcomp(string &ip, string &dup, char A, char G, int b) {
  int ans = 0;
  for (int i = 0; i < b; i++) {
    dup[i] = ((i & 1) == 0) ? A : G;
    ans += (ip[i] == dup[i]) ? 0 : 1;
  }
  return ans;
}
int solve(vector<string> &ip, vector<string> &dup, int a, int b,
          string letters) {
  char A = letters[0], G = letters[1];
  char C = letters[2], T = letters[3];
  int ans = 0;
  for (int i = 0; i < a; i++) {
    swap(A, C);
    swap(G, T);
    int w1 = fillandcomp(ip[i], dup[i], A, G, b);
    int w2 = fillandcomp(ip[i], dup[i], G, A, b);
    if (w1 < w2) fillandcomp(ip[i], dup[i], A, G, b);
    ans += min(w1, w2);
  }
  return ans;
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(NULL);
  cout.tie(NULL);
  int n, m;
  cin >> n >> m;
  for (int i = 0; i < n; i++) cin >> inp[i];
  transpose(n, m);
  for (int i = 0; i < n; i++) place1[i].resize(m);
  for (int i = 0; i < m; i++) place2[i].resize(n);
  string letters = "AGCT";
  string lseq;
  int ans = INT_MAX, tr = -1;
  do {
    int tempans = solve(inp, place1, n, m, letters);
    if (tempans < ans) {
      lseq = letters;
      tr = 0;
      ans = tempans;
    }
    tempans = solve(transposeinp, place2, m, n, letters);
    if (tempans < ans) {
      lseq = letters;
      tr = 1;
      ans = tempans;
    }
  } while (next_permutation(letters.begin(), letters.end()));
  if (!tr) {
    solve(inp, place1, n, m, lseq);
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) cout << place1[i][j];
      cout << endl;
    }
  } else {
    solve(transposeinp, place2, m, n, lseq);
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) cout << place2[j][i];
      cout << endl;
    }
  }
  return 0;
}
