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 r, c;
string g[200000];
string alpha = "ACGT";
void rowSolve(vector<vector<char>>& ret, string even, string odd, int& cost) {
  ret.resize(r);
  for (int i = 0; i < r; i++) {
    string match = i % 2 == 0 ? even : odd;
    int normalCost = 0;
    int flipCost = 0;
    for (int j = 0; j < c; j++) {
      if (g[i][j] != match[j % 2]) normalCost++;
      if (g[i][j] != match[1 ^ (j % 2)]) flipCost++;
    }
    cost += min(normalCost, flipCost);
    if (normalCost < flipCost) {
      for (int j = 0; j < c; j++) {
        ret[i].push_back(match[j % 2]);
      }
    } else {
      for (int j = 0; j < c; j++) {
        ret[i].push_back(match[1 ^ (j % 2)]);
      }
    }
  }
}
void colSolve(vector<vector<char>>& ret, string even, string odd, int& cost) {
  ret.resize(r);
  for (int j = 0; j < c; j++) {
    string match = j % 2 == 0 ? even : odd;
    int normalCost = 0;
    int flipCost = 0;
    for (int i = 0; i < r; i++) {
      if (g[i][j] != match[i % 2]) normalCost++;
      if (g[i][j] != match[1 ^ (i % 2)]) flipCost++;
    }
    cost += min(normalCost, flipCost);
    if (normalCost < flipCost) {
      for (int i = 0; i < r; i++) {
        ret[i].push_back(match[i % 2]);
      }
    } else {
      for (int i = 0; i < r; i++) {
        ret[i].push_back(match[1 ^ (i % 2)]);
      }
    }
  }
}
void solve() {
  cin >> r >> c;
  for (int i = 0; i < r; i++) {
    cin >> g[i];
  }
  vector<vector<char>> ret;
  int cost = 1e9;
  for (int aPair = 1; aPair < alpha.size(); aPair++) {
    string even = "A";
    even += alpha[aPair];
    string odd = "";
    for (int i = 1; i < 4; i++) {
      if (i != aPair) odd += alpha[i];
    }
    {
      int currCost = 0;
      vector<vector<char>> cand;
      rowSolve(cand, even, odd, currCost);
      if (currCost < cost) {
        ret = cand;
        cost = currCost;
      }
    }
    {
      int currCost = 0;
      vector<vector<char>> cand;
      rowSolve(cand, odd, even, currCost);
      if (currCost < cost) {
        ret = cand;
        cost = currCost;
      }
    }
    {
      int currCost = 0;
      vector<vector<char>> cand;
      colSolve(cand, even, odd, currCost);
      if (currCost < cost) {
        ret = cand;
        cost = currCost;
      }
    }
    {
      int currCost = 0;
      vector<vector<char>> cand;
      colSolve(cand, odd, even, currCost);
      if (currCost < cost) {
        ret = cand;
        cost = currCost;
      }
    }
  }
  for (int i = 0; i < r; i++) {
    for (int j = 0; j < c; j++) {
      cout << ret[i][j];
    }
    cout << "\n";
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  solve();
}
