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;
char arr[4] = {'A', 'C', 'G', 'T'};
int ans = 1000000006LL;
string s[300005];
int n, m;
int isrow;
vector<int> anslist;
int ansa, ansb;
void rowfixed(int a, int b) {
  vector<int> collist;
  int c, d;
  for (int i = 0; i < 4; i++) {
    if (i != a && i != b) {
      c = i;
      d = 6 - a - b - c;
      break;
    }
  }
  int xx = 0;
  for (int i = 0; i < n; i++) {
    int x = 0, y = 0;
    if (i & 1) {
      for (int j = 0; j < m; j += 2) {
        if (s[i][j] != arr[a]) x++;
        if (s[i][j] != arr[b]) y++;
      }
      for (int j = 1; j < m; j += 2) {
        if (s[i][j] != arr[a]) y++;
        if (s[i][j] != arr[b]) x++;
      }
    } else {
      for (int j = 0; j < m; j += 2) {
        if (s[i][j] != arr[c]) x++;
        if (s[i][j] != arr[d]) y++;
      }
      for (int j = 1; j < m; j += 2) {
        if (s[i][j] != arr[c]) y++;
        if (s[i][j] != arr[d]) x++;
      }
    }
    xx += min(x, y);
    if (x < y) {
      collist.push_back((i & 1) ? a : c);
    } else {
      collist.push_back((i & 1) ? b : d);
    }
  }
  if (xx < ans) {
    isrow = 1;
    anslist = collist;
    ansb = collist[1] == a ? b : a;
    ansa = collist[0] == c ? d : c;
    ans = xx;
  }
}
void columnfixed(int a, int b) {
  vector<int> rowlist;
  int c, d;
  for (int i = 0; i < 4; i++) {
    if (i != a && i != b) {
      c = i;
      d = 6 - a - b - c;
      break;
    }
  }
  int xx = 0;
  for (int j = 0; j < m; j++) {
    int x = 0, y = 0;
    if (j & 1) {
      for (int i = 0; i < n; i += 2) {
        if (s[i][j] != arr[a]) x++;
        if (s[i][j] != arr[b]) y++;
      }
      for (int i = 1; i < n; i += 2) {
        if (s[i][j] != arr[a]) y++;
        if (s[i][j] != arr[b]) x++;
      }
    } else {
      for (int i = 0; i < n; i += 2) {
        if (s[i][j] != arr[c]) x++;
        if (s[i][j] != arr[d]) y++;
      }
      for (int i = 1; i < n; i += 2) {
        if (s[i][j] != arr[c]) y++;
        if (s[i][j] != arr[d]) x++;
      }
    }
    xx += min(x, y);
    if (x < y) {
      rowlist.push_back((j & 1) ? a : c);
    } else {
      rowlist.push_back((j & 1) ? b : d);
    }
  }
  if (xx < ans) {
    isrow = 0;
    anslist = rowlist;
    ansb = rowlist[1] == a ? b : a;
    ansa = rowlist[0] == c ? d : c;
    ans = xx;
  }
}
void print() {
  if (isrow) {
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        if (j & 1) {
          if (i & 1)
            cout << arr[(anslist[i] == ansb) ? anslist[1] : ansb];
          else
            cout << arr[(anslist[i] == ansa) ? anslist[0] : ansa];
        } else
          cout << arr[anslist[i]];
      }
      cout << endl;
    }
  } else {
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        if (i & 1) {
          if (j & 1)
            cout << arr[(anslist[j] == ansb) ? anslist[1] : ansb];
          else
            cout << arr[(anslist[j] == ansa) ? anslist[0] : ansa];
        } else
          cout << arr[anslist[j]];
      }
      cout << endl;
    }
  }
}
int main() {
  cin >> n >> m;
  for (int i = 0; i < n; i++) cin >> s[i];
  for (int i = 0; i < 4; i++) {
    for (int j = i + 1; j < 4; j++) {
      rowfixed(i, j);
      columnfixed(i, j);
    }
  }
  print();
  return 0;
}
