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 INF = 500000;
int n, m;
vector<char> board[300010];
vector<int> row[300010];
vector<int> col[300010];
string str[6];
int main() {
  str[0] = "ACTG";
  str[1] = "ATCG";
  str[2] = "AGCT";
  str[3] = "CTAG";
  str[4] = "CGAT";
  str[5] = "TGAC";
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  cin >> n >> m;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      char x;
      cin >> x;
      board[i].push_back(x);
    }
  }
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < 12; j++) row[i].push_back(0);
    for (int j = 0; j < m; j++) {
      if (j % 2 == 0) {
        if (board[i][j] == 'A') {
          row[i][0]++;
          row[i][1]++;
          row[i][2]++;
        } else if (board[i][j] == 'C') {
          row[i][3]++;
          row[i][4]++;
          row[i][6]++;
        } else if (board[i][j] == 'T') {
          row[i][5]++;
          row[i][7]++;
          row[i][9]++;
        } else {
          row[i][8]++;
          row[i][10]++;
          row[i][11]++;
        }
      } else {
        if (board[i][j] == 'A') {
          row[i][6]++;
          row[i][7]++;
          row[i][8]++;
        } else if (board[i][j] == 'C') {
          row[i][0]++;
          row[i][9]++;
          row[i][10]++;
        } else if (board[i][j] == 'T') {
          row[i][1]++;
          row[i][3]++;
          row[i][11]++;
        } else {
          row[i][2]++;
          row[i][4]++;
          row[i][5]++;
        }
      }
    }
  }
  for (int j = 0; j < m; j++) {
    for (int i = 0; i < 12; i++) col[j].push_back(0);
    for (int i = 0; i < n; i++) {
      if (i % 2 == 0) {
        if (board[i][j] == 'A') {
          col[j][0]++;
          col[j][1]++;
          col[j][2]++;
        } else if (board[i][j] == 'C') {
          col[j][3]++;
          col[j][4]++;
          col[j][6]++;
        } else if (board[i][j] == 'T') {
          col[j][5]++;
          col[j][7]++;
          col[j][9]++;
        } else {
          col[j][8]++;
          col[j][10]++;
          col[j][11]++;
        }
      } else {
        if (board[i][j] == 'A') {
          col[j][6]++;
          col[j][7]++;
          col[j][8]++;
        } else if (board[i][j] == 'C') {
          col[j][0]++;
          col[j][9]++;
          col[j][10]++;
        } else if (board[i][j] == 'T') {
          col[j][1]++;
          col[j][3]++;
          col[j][11]++;
        } else {
          col[j][2]++;
          col[j][4]++;
          col[j][5]++;
        }
      }
    }
  }
  int r[6] = {};
  int c[6] = {};
  for (int i = 0; i < n; i++) {
    if (i % 2 == 0) {
      r[0] += max(row[i][0], row[i][6]);
      r[1] += max(row[i][1], row[i][7]);
      r[2] += max(row[i][2], row[i][8]);
      r[3] += max(row[i][3], row[i][9]);
      r[4] += max(row[i][4], row[i][10]);
      r[5] += max(row[i][5], row[i][11]);
    } else {
      r[0] += max(row[i][5], row[i][11]);
      r[1] += max(row[i][4], row[i][10]);
      r[2] += max(row[i][3], row[i][9]);
      r[3] += max(row[i][2], row[i][8]);
      r[4] += max(row[i][1], row[i][7]);
      r[5] += max(row[i][0], row[i][6]);
    }
  }
  for (int i = 0; i < m; i++) {
    if (i % 2 == 0) {
      c[0] += max(col[i][0], col[i][6]);
      c[1] += max(col[i][1], col[i][7]);
      c[2] += max(col[i][2], col[i][8]);
      c[3] += max(col[i][3], col[i][9]);
      c[4] += max(col[i][4], col[i][10]);
      c[5] += max(col[i][5], col[i][11]);
    } else {
      c[0] += max(col[i][5], col[i][11]);
      c[1] += max(col[i][4], col[i][10]);
      c[2] += max(col[i][3], col[i][9]);
      c[3] += max(col[i][2], col[i][8]);
      c[4] += max(col[i][1], col[i][7]);
      c[5] += max(col[i][0], col[i][6]);
    }
  }
  if (*max_element(r, r + 6) > *max_element(c, c + 6)) {
    int id = max_element(r, r + 6) - r;
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        if (i % 2 == 0 && j % 2 == 0)
          board[i][j] =
              ((row[i][id] > row[i][id + 6]) ? str[id][0] : str[id][1]);
        else if (i % 2 == 0 && j % 2 == 1)
          board[i][j] =
              ((row[i][id] > row[i][id + 6]) ? str[id][1] : str[id][0]);
        else if (i % 2 == 1 && j % 2 == 0)
          board[i][j] =
              ((row[i][5 - id] > row[i][11 - id]) ? str[id][2] : str[id][3]);
        else
          board[i][j] =
              ((row[i][5 - id] > row[i][11 - id]) ? str[id][3] : str[id][2]);
      }
    }
  } else {
    int id = max_element(c, c + 6) - c;
    for (int j = 0; j < m; j++) {
      for (int i = 0; i < n; i++) {
        if (j % 2 == 0 && i % 2 == 0)
          board[i][j] =
              ((col[j][id] > col[j][id + 6]) ? str[id][0] : str[id][1]);
        else if (j % 2 == 0 && i % 2 == 1)
          board[i][j] =
              ((col[j][id] > col[j][id + 6]) ? str[id][1] : str[id][0]);
        else if (j % 2 == 1 && i % 2 == 0)
          board[i][j] =
              ((col[j][5 - id] > col[j][11 - id]) ? str[id][2] : str[id][3]);
        else
          board[i][j] =
              ((col[j][5 - id] > col[j][11 - id]) ? str[id][3] : str[id][2]);
      }
    }
  }
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      cout << board[i][j];
    }
    cout << endl;
  }
}
