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;
const long long INF = 1e9;
const long long MOD = 1e9 + 7;
int n, m;
vector<string> A;
vector<string> pem;
vector<string> res;
string second;
int now[4];
bool sudah[4];
char aw[4] = {'A', 'T', 'C', 'G'};
int mins = INF;
void permut(int sek) {
  if (sek == 4) {
    if (!(now[0] <= now[1] && now[2] <= now[3])) return;
    int tot = 0;
    for (int i = 0; i < m; i += 2) {
      int satu = 0;
      for (int j = 0; j < n; j += 2) {
        if (A[j][i] != aw[now[0]]) satu++;
        if (j + 1 < n && A[j + 1][i] != aw[now[1]]) satu++;
      }
      int dua = 0;
      for (int j = 0; j < n; j += 2) {
        if (A[j][i] != aw[now[1]]) dua++;
        if (j + 1 < n && A[j + 1][i] != aw[now[0]]) dua++;
      }
      if (satu <= dua) {
        for (int j = 0; j < n; j += 2) {
          pem[j][i] = aw[now[0]];
          if (j + 1 < n) pem[j + 1][i] = aw[now[1]];
        }
        tot += satu;
      } else {
        for (int j = 0; j < n; j += 2) {
          pem[j][i] = aw[now[1]];
          if (j + 1 < n) pem[j + 1][i] = aw[now[0]];
        }
        tot += dua;
      }
    }
    for (int i = 1; i < m; i += 2) {
      int satu = 0;
      for (int j = 0; j < n; j += 2) {
        if (A[j][i] != aw[now[2]]) satu++;
        if (j + 1 < n && A[j + 1][i] != aw[now[3]]) satu++;
      }
      int dua = 0;
      for (int j = 0; j < n; j += 2) {
        if (A[j][i] != aw[now[3]]) dua++;
        if (j + 1 < n && A[j + 1][i] != aw[now[2]]) dua++;
      }
      if (satu <= dua) {
        for (int j = 0; j < n; j += 2) {
          pem[j][i] = aw[now[2]];
          if (j + 1 < n) pem[j + 1][i] = aw[now[3]];
        }
        tot += satu;
      } else {
        for (int j = 0; j < n; j += 2) {
          pem[j][i] = aw[now[3]];
          if (j + 1 < n) pem[j + 1][i] = aw[now[2]];
        }
        tot += dua;
      }
    }
    if (tot < mins) {
      mins = tot;
      res = pem;
    }
    tot = 0;
    for (int i = 0; i < n; i += 2) {
      int satu = 0;
      for (int j = 0; j < m; j += 2) {
        if (A[i][j] != aw[now[0]]) satu++;
        if (j + 1 < m && A[i][j + 1] != aw[now[1]]) satu++;
      }
      int dua = 0;
      for (int j = 0; j < m; j += 2) {
        if (A[i][j] != aw[now[1]]) dua++;
        if (j + 1 < m && A[i][j + 1] != aw[now[0]]) dua++;
      }
      if (satu <= dua) {
        for (int j = 0; j < m; j += 2) {
          pem[i][j] = aw[now[0]];
          if (j + 1 < m) pem[i][j + 1] = aw[now[1]];
        }
        tot += satu;
      } else {
        for (int j = 0; j < m; j += 2) {
          pem[i][j] = aw[now[1]];
          if (j + 1 < m) pem[i][j + 1] = aw[now[0]];
        }
        tot += dua;
      }
    }
    for (int i = 1; i < n; i += 2) {
      int satu = 0;
      for (int j = 0; j < m; j += 2) {
        if (A[i][j] != aw[now[2]]) satu++;
        if (j + 1 < m && A[i][j + 1] != aw[now[3]]) satu++;
      }
      int dua = 0;
      for (int j = 0; j < m; j += 2) {
        if (A[i][j] != aw[now[3]]) dua++;
        if (j + 1 < m && A[i][j + 1] != aw[now[2]]) dua++;
      }
      if (satu <= dua) {
        for (int j = 0; j < m; j += 2) {
          pem[i][j] = aw[now[2]];
          if (j + 1 < m) pem[i][j + 1] = aw[now[3]];
        }
        tot += satu;
      } else {
        for (int j = 0; j < m; j += 2) {
          pem[i][j] = aw[now[3]];
          if (j + 1 < m) pem[i][j + 1] = aw[now[2]];
        }
        tot += dua;
      }
    }
    if (tot < mins) {
      mins = tot;
      res = pem;
    }
    return;
  }
  for (int i = 0; i < 4; i++) {
    if (sudah[i] == 0) {
      sudah[i] = 1;
      now[sek] = i;
      permut(sek + 1);
      sudah[i] = 0;
    }
  }
}
int main() {
  cin >> n >> m;
  for (int i = 0; i < n; i++) {
    cin >> second;
    A.push_back(second);
    pem.push_back(second);
  }
  permut(0);
  for (int i = 0; i < res.size(); i++) cout << res[i] << '\n';
}
