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;
ifstream fin("input.txt");
ofstream fout("output.txt");
bool isPrime(long long int x) {
  if (x <= 4 || x % 2 == 0 || x % 3 == 0) return x == 2 || x == 3;
  for (int i = 5; i * i <= x; i += 6)
    if (x % i == 0 || x % (i + 2) == 0) return 0;
  return 1;
}
int NumDigits(int x) {
  return (
      x < 10
          ? 1
          : (x < 100
                 ? 2
                 : (x < 1000
                        ? 3
                        : (x < 10000
                               ? 4
                               : (x < 100000
                                      ? 5
                                      : (x < 1000000
                                             ? 6
                                             : (x < 10000000
                                                    ? 7
                                                    : (x < 100000000
                                                           ? 8
                                                           : (x < 1000000000
                                                                  ? 9
                                                                  : 10)))))))));
}
inline void boostIO() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cout.precision(10);
}
inline long long int Pow10(int x) {
  if (x == 0) return 1;
  if (x == 1) return 10;
  if (x == 2) return 100;
  if (x == 3) return 1000;
  if (x == 4) return 10000;
  if (x == 5) return 100000;
  if (x == 6) return 1000000;
  if (x == 7) return 10000000;
  if (x == 8) return 100000000;
  if (x == 9) return 1000000000;
  if (x == 10) return 10000000000;
}
long long int gcd(long long int a, long long int b) {
  return b ? gcd(b, a % b) : a;
}
long long int lcm(long long int a, long long int b) {
  return a * b / gcd(a, b);
}
long long MOD = 1e9 + 7;
long long n, m;
long long f(char a, char b, char c, char d, vector<vector<char>> &A) {
  char V[4][2] = {{a, b}, {c, d}, {b, a}, {d, c}};
  char z;
  long long dif = 0;
  for (long long i = 0; i < (n); ++i) {
    long long case0 = 0;
    long long case1 = 0;
    for (long long j = 0; j < (m); ++j) {
      z = V[i % 4][j % 2];
      if (A[i][j] != z) case0++;
    }
    for (long long j = 0; j < (m); ++j) {
      z = V[i % 4][(j + 1) % 2];
      if (A[i][j] != z) case1++;
    }
    if (case0 <= case1) {
      dif += case0;
    } else {
      dif += case1;
    }
  }
  return dif;
}
long long f2(char a, char b, char c, char d, vector<vector<char>> &A) {
  char V[4][2] = {{a, b}, {c, d}, {b, a}, {d, c}};
  char z;
  long long dif = 0;
  for (long long i = 0; i < (m); ++i) {
    long long case0 = 0;
    long long case1 = 0;
    for (long long j = 0; j < (n); ++j) {
      z = V[i % 4][j % 2];
      if (A[j][i] != z) case0++;
    }
    for (long long j = 0; j < (n); ++j) {
      z = V[i % 4][(j + 1) % 2];
      if (A[j][i] != z) case1++;
    }
    if (case0 <= case1) {
      dif += case0;
    } else {
      dif += case1;
    }
  }
  return dif;
}
void Out(char a, char b, char c, char d, vector<vector<char>> &Q,
         vector<vector<char>> &A) {
  char V[4][2] = {{a, b}, {c, d}, {b, a}, {d, c}};
  char z;
  long long dif = 0;
  for (long long i = 0; i < (n); ++i) {
    long long case0 = 0;
    long long case1 = 0;
    for (long long j = 0; j < (m); ++j) {
      z = V[i % 4][j % 2];
      if (A[i][j] != z) case0++;
    }
    for (long long j = 0; j < (m); ++j) {
      z = V[i % 4][(j + 1) % 2];
      if (A[i][j] != z) case1++;
    }
    if (case0 <= case1) {
      for (long long j = 0; j < (m); ++j) {
        z = V[i % 4][j % 2];
        Q[i][j] = z;
      }
    } else {
      for (long long j = 0; j < (m); ++j) {
        z = V[i % 4][(j + 1) % 2];
        Q[i][j] = z;
      }
    }
  }
}
void Out2(char a, char b, char c, char d, vector<vector<char>> &Q,
          vector<vector<char>> &A) {
  char V[4][2] = {{a, b}, {c, d}, {b, a}, {d, c}};
  char z;
  long long dif = 0;
  for (long long i = 0; i < (m); ++i) {
    long long case0 = 0;
    long long case1 = 0;
    for (long long j = 0; j < (n); ++j) {
      z = V[i % 4][j % 2];
      if (A[j][i] != z) case0++;
    }
    for (long long j = 0; j < (n); ++j) {
      z = V[i % 4][(j + 1) % 2];
      if (A[j][i] != z) case1++;
    }
    if (case0 <= case1) {
      for (long long j = 0; j < (n); ++j) {
        z = V[i % 4][j % 2];
        Q[j][i] = z;
      }
    } else {
      for (long long j = 0; j < (n); ++j) {
        z = V[i % 4][(j + 1) % 2];
        Q[j][i] = z;
      }
    }
  }
}
bool chosen[4];
vector<char> p;
char W[4];
bool ot = 0;
long long Min = LONG_LONG_MAX;
vector<char> e;
void search(vector<vector<char>> &A) {
  if (p.size() == 4) {
    long long v = f(p[0], p[1], p[2], p[3], A);
    if (v < Min) {
      Min = v;
      e = p;
      ot = 0;
    }
    v = f2(p[0], p[1], p[2], p[3], A);
    if (v < Min) {
      Min = v;
      e = p;
      ot = 1;
    }
  } else {
    for (long long i = 0; i < 4; ++i) {
      if (chosen[i]) continue;
      chosen[i] = true;
      p.push_back(W[i]);
      search(A);
      chosen[i] = false;
      p.pop_back();
    }
  }
}
int32_t main() {
  boostIO();
  cin >> n >> m;
  vector<vector<char>> A(n, vector<char>(m));
  for (long long i = 0; i < (n); ++i) {
    for (long long j = 0; j < (m); ++j) {
      cin >> A[i][j];
    }
  }
  W[0] = 'A';
  W[1] = 'G';
  W[2] = 'C';
  W[3] = 'T';
  search(A);
  vector<vector<char>> Q(n, vector<char>(m));
  if (ot == 0)
    Out(e[0], e[1], e[2], e[3], Q, A);
  else {
    Out2(e[0], e[1], e[2], e[3], Q, A);
  }
  for (long long i = 0; i < (n); ++i) {
    for (long long j = 0; j < (m); ++j) {
      cout << Q[i][j];
    }
    cout << '\n';
  }
  cerr << '\n' << "RUNTIME: " << 1.0 * clock() / CLOCKS_PER_SEC << " s" << '\n';
  return 0;
}
