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>
#pragma comment(linker, "/stack:225450978")
#pragma GCC optimize("Ofast")
using namespace std;
const long long Mod = 1000000007LL, INF = 1e9, LINF = 1e18;
const long double Pi = 3.141592653589793116, EPS = 1e-9,
                  Gold = ((1 + sqrt(5)) / 2);
long long keymod[] = {1000000007LL, 1000000009LL, 1000000021LL, 1000000033LL};
long long keyCount = sizeof(keymod) / sizeof(long long);
mt19937 rng32(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rng64(chrono::steady_clock::now().time_since_epoch().count());
template <class T>
int getbit(T s, int i) {
  return (s >> i) & 1;
}
template <class T>
T onbit(T s, int i) {
  return s | (T(1) << i);
}
template <class T>
T offbit(T s, int i) {
  return s & (~(T(1) << i));
}
template <class T>
int cntbit(T s) {
  return __builtin_popcountll(s);
}
auto TimeStart = chrono::steady_clock::now();
auto TimeEnd = chrono::steady_clock::now();
void ControlIO(int argc, char* argv[]);
void TimerStart();
void TimerStop();
void Exit();
string cppstr_infile = "FILE.IN";
string cppstr_outfile = "FILE.OUT";
long long n, m;
vector<vector<char> > A;
map<char, int> Map;
vector<char> IMap(4);
long long MinDiff = LINF;
vector<vector<char> > OptimalTable;
long long Differs(vector<vector<char> >& Table1,
                  vector<vector<char> >& Table2) {
  long long res = 0;
  for (long long i = 0; i < n; i++) {
    for (long long j = 0; j < m; j++) {
      res += (Table1[i][j] != Table2[i][j]);
    }
  }
  return res;
}
void Input() {
  cin >> n >> m;
  A.resize(n, vector<char>(m));
  for (long long i = 0; i < n; i++) {
    for (long long j = 0; j < m; j++) {
      cin >> A[i][j];
    }
  }
  Map['A'] = 0;
  Map['T'] = 1;
  Map['G'] = 2;
  Map['C'] = 3;
  IMap[0] = 'A';
  IMap[1] = 'T';
  IMap[2] = 'G';
  IMap[3] = 'C';
}
void Solve() {
  for (long long i = 0; i < 4; i++) {
    for (long long j = 0; j < 4; j++) {
      if (j == i) continue;
      for (long long k = 0; k < 4; k++) {
        if (k == i) continue;
        if (k == j) continue;
        for (long long l = 0; l < 4; l++) {
          if (l == i) continue;
          if (l == j) continue;
          if (l == k) continue;
          vector<string> pattern(2, "");
          pattern[0] += IMap[i];
          pattern[0] += IMap[j];
          pattern[1] += IMap[k];
          pattern[1] += IMap[l];
          vector<vector<char> > Sample(n, vector<char>(m));
          for (long long i = 0; i < n; i++) {
            vector<long long> subdiff(2, 0);
            for (long long j = 0; j < m; j++) {
              subdiff[0] += (pattern[i % 2][j % 2] != A[i][j]);
              subdiff[1] += (pattern[i % 2][1 - j % 2] != A[i][j]);
            }
            if (subdiff[0] <= subdiff[1])
              for (long long j = 0; j < m; j++)
                Sample[i][j] = pattern[i % 2][j % 2];
            else
              for (long long j = 0; j < m; j++)
                Sample[i][j] = pattern[i % 2][1 - j % 2];
          }
          long long Diff = Differs(Sample, A);
          if (Diff < MinDiff) {
            MinDiff = Diff;
            OptimalTable = Sample;
          }
        }
      }
    }
  }
  for (long long i = 0; i < 4; i++) {
    for (long long j = 0; j < 4; j++) {
      if (j == i) continue;
      for (long long k = 0; k < 4; k++) {
        if (k == i) continue;
        if (k == j) continue;
        for (long long l = 0; l < 4; l++) {
          if (l == i) continue;
          if (l == j) continue;
          if (l == k) continue;
          vector<string> pattern(2, "");
          pattern[0] += IMap[i];
          pattern[0] += IMap[j];
          pattern[1] += IMap[k];
          pattern[1] += IMap[l];
          vector<vector<char> > Sample(n, vector<char>(m));
          for (long long j = 0; j < m; j++) {
            vector<long long> subdiff(2, 0);
            for (long long i = 0; i < n; i++) {
              subdiff[0] += (pattern[j % 2][i % 2] != A[i][j]);
              subdiff[1] += (pattern[j % 2][1 - i % 2] != A[i][j]);
            }
            if (subdiff[0] <= subdiff[1])
              for (long long i = 0; i < n; i++)
                Sample[i][j] = pattern[j % 2][i % 2];
            else
              for (long long i = 0; i < n; i++)
                Sample[i][j] = pattern[j % 2][1 - i % 2];
          }
          long long Diff = Differs(Sample, A);
          if (Diff < MinDiff) {
            MinDiff = Diff;
            OptimalTable = Sample;
          }
        }
      }
    }
  }
  for (auto Row : OptimalTable) {
    for (auto Cell : Row) cout << Cell;
    cout << '\n';
  }
}
int main(int argc, char* argv[]) {
  ControlIO(argc, argv);
  ios_base::sync_with_stdio(0);
  cin.tie(NULL);
  Input();
  TimerStart();
  Solve();
  TimerStop();
  return 0;
}
void ControlIO(int argc, char* argv[]) {
  char* infile = new char[cppstr_infile.size() + 1];
  char* outfile = new char[cppstr_outfile.size() + 1];
  strcpy(infile, cppstr_infile.c_str());
  strcpy(outfile, cppstr_outfile.c_str());
}
void TimerStart() {}
void TimerStop() {}
void Exit() {
  TimerStop();
  exit(0);
}
