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 int kInf = numeric_limits<int>::max();
string chrs = "ACGT";
int n, m, minDiff = kInf, p[5];
vector<string> conf, finConf;
int getColumnCost(int col, char c1, char c2) {
  int cost = 0;
  for (int i = 0; i < n; i++) {
    if (i % 2 == 0 && conf[i][col] != c1) {
      cost++;
    }
    if (i % 2 == 1 && conf[i][col] != c2) {
      cost++;
    }
  }
  return cost;
}
void applyColumn(vector<string>& crtConf, int col, char c1, char c2) {
  for (int i = 0; i < n; i++) {
    if (i % 2 == 0) {
      crtConf[i][col] = c1;
    } else {
      crtConf[i][col] = c2;
    }
  }
}
int solveColumn(vector<string>& crtConf, int col, char c1, char c2) {
  int diff12 = getColumnCost(col, c1, c2);
  int diff21 = getColumnCost(col, c2, c1);
  if (diff12 < diff21) {
    applyColumn(crtConf, col, c1, c2);
  } else {
    applyColumn(crtConf, col, c2, c1);
  }
  return min(diff12, diff21);
}
void tryVert(char c1, char c2, char c3, char c4) {
  vector<string> crtConf(n, string(m, ' '));
  int crtDiff = 0;
  for (int j = 0; j < m; j++) {
    if (j % 2 == 0) {
      crtDiff += solveColumn(crtConf, j, c1, c2);
    } else {
      crtDiff += solveColumn(crtConf, j, c3, c4);
    }
  }
  if (crtDiff < minDiff) {
    minDiff = crtDiff;
    finConf = crtConf;
  }
}
int getLineCost(int line, char c1, char c2) {
  int cost = 0;
  for (int i = 0; i < m; i++) {
    if (i % 2 == 0 && conf[line][i] != c1) {
      cost++;
    }
    if (i % 2 == 1 && conf[line][i] != c2) {
      cost++;
    }
  }
  return cost;
}
void applyLine(vector<string>& crtConf, int line, char c1, char c2) {
  for (int i = 0; i < m; i++) {
    if (i % 2 == 0) {
      crtConf[line][i] = c1;
    } else {
      crtConf[line][i] = c2;
    }
  }
}
int solveLine(vector<string>& crtConf, int line, char c1, char c2) {
  int diff12 = getLineCost(line, c1, c2);
  int diff21 = getLineCost(line, c2, c1);
  if (diff12 < diff21) {
    applyLine(crtConf, line, c1, c2);
  } else {
    applyLine(crtConf, line, c2, c1);
  }
  return min(diff12, diff21);
}
void tryHoriz(char c1, char c2, char c3, char c4) {
  vector<string> crtConf(n, string(m, ' '));
  int crtDiff = 0;
  for (int i = 0; i < n; i++) {
    if (i % 2 == 0) {
      crtDiff += solveLine(crtConf, i, c1, c2);
    } else {
      crtDiff += solveLine(crtConf, i, c3, c4);
    }
  }
  if (crtDiff < minDiff) {
    minDiff = crtDiff;
    finConf = crtConf;
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cin >> n >> m;
  for (int i = 0; i < n; i++) {
    string line;
    cin >> line;
    conf.push_back(line);
  }
  for (int i = 0; i < 4; i++) {
    p[i] = i;
  }
  do {
    tryVert(chrs[p[0]], chrs[p[1]], chrs[p[2]], chrs[p[3]]);
  } while (next_permutation(p, p + 4));
  for (int i = 0; i < 4; i++) {
    p[i] = i;
  }
  do {
    tryHoriz(chrs[p[0]], chrs[p[1]], chrs[p[2]], chrs[p[3]]);
  } while (next_permutation(p, p + 4));
  for (int i = 0; i < n; i++) {
    cout << finConf[i] << "\n";
  }
}
