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 MOD = 1000000007;
double PI = 4 * atan(1);
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int n, m;
  cin >> n >> m;
  int grid[300005];
  map<char, int> con;
  con['A'] = 0;
  con['G'] = 1;
  con['C'] = 2;
  con['T'] = 3;
  map<int, char> noc;
  noc[0] = 'A';
  noc[1] = 'G';
  noc[2] = 'C';
  noc[3] = 'T';
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      char c;
      cin >> c;
      grid[i * m + j] = con[c];
    }
  }
  int minchange = MOD;
  int dirchange = 0;
  int bestgrid[300005];
  for (int a = 0; a < 4; a++) {
    for (int b = a + 1; b < 4; b++) {
      dirchange = 0;
      int tempgrid[300005] = {};
      for (int i = 0; i < n; i++) {
        char l1;
        char l2;
        if (i % 2 == 0) {
          l1 = a;
          l2 = b;
        } else {
          for (int k = 0; k < 4; k++) {
            if (a != k && b != k) {
              l1 = k;
            }
          }
          for (int k = 0; k < 4; k++) {
            if (a != k && b != k && l1 != k) {
              l2 = k;
            }
          }
        }
        int rowchange1 = 0;
        for (int j = 0; j < m; j++) {
          if (j % 2 == 0) {
            if (grid[i * m + j] != l1) {
              rowchange1 += 1;
            }
          } else {
            if (grid[i * m + j] != l2) {
              rowchange1 += 1;
            }
          }
        }
        int rowchange2 = 0;
        swap(l1, l2);
        for (int j = 0; j < m; j++) {
          if (j % 2 == 0) {
            if (grid[i * m + j] != l1) {
              rowchange2 += 1;
            }
          } else {
            if (grid[i * m + j] != l2) {
              rowchange2 += 1;
            }
          }
        }
        dirchange += min(rowchange1, rowchange2);
        if (rowchange1 < rowchange2) {
          swap(l1, l2);
        }
        for (int j = 0; j < m; j++) {
          if (j % 2 == 0) {
            tempgrid[i * m + j] = l1;
          } else {
            tempgrid[i * m + j] = l2;
          }
        }
      }
      if (dirchange < minchange) {
        minchange = dirchange;
        for (int i = 0; i < n; i++) {
          for (int j = 0; j < m; j++) {
            bestgrid[i * m + j] = tempgrid[i * m + j];
          }
        }
      }
    }
  }
  dirchange = 0;
  for (int a = 0; a < 4; a++) {
    for (int b = a + 1; b < 4; b++) {
      dirchange = 0;
      int tempgrid[300005] = {};
      for (int i = 0; i < m; i++) {
        char l1;
        char l2;
        if (i % 2 == 0) {
          l1 = a;
          l2 = b;
        } else {
          for (int k = 0; k < 4; k++) {
            if (a != k && b != k) {
              l1 = k;
            }
          }
          for (int k = 0; k < 4; k++) {
            if (a != k && b != k && l1 != k) {
              l2 = k;
            }
          }
        }
        int rowchange1 = 0;
        for (int j = 0; j < n; j++) {
          if (j % 2 == 0) {
            if (grid[j * m + i] != l1) {
              rowchange1 += 1;
            }
          } else {
            if (grid[j * m + i] != l2) {
              rowchange1 += 1;
            }
          }
        }
        int rowchange2 = 0;
        swap(l1, l2);
        for (int j = 0; j < n; j++) {
          if (j % 2 == 0) {
            if (grid[j * m + i] != l1) {
              rowchange2 += 1;
            }
          } else {
            if (grid[j * m + i] != l2) {
              rowchange2 += 1;
            }
          }
        }
        dirchange += min(rowchange1, rowchange2);
        if (rowchange1 < rowchange2) {
          swap(l1, l2);
        }
        for (int j = 0; j < n; j++) {
          if (j % 2 == 0) {
            tempgrid[j * m + i] = l1;
          } else {
            tempgrid[j * m + i] = l2;
          }
        }
      }
      if (dirchange < minchange) {
        minchange = dirchange;
        for (int i = 0; i < n; i++) {
          for (int j = 0; j < m; j++) {
            bestgrid[i * m + j] = tempgrid[i * m + j];
          }
        }
      }
    }
  }
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      cout << noc[bestgrid[i * m + j]];
    }
    cout << '\n';
    ;
  }
  return 0;
}
