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 GCC optimize("Ofast,unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
long long sqr(long long x) { return x * x; }
long double sqrd(long double x) { return x * x; }
inline long long gcd(long long a, long long b) {
  while (b) {
    a %= b, swap(a, b);
  }
  return a;
}
inline long long lcm(long long a, long long b) {
  return a * b / max(1ll, gcd(a, b));
}
mt19937 Random((long long)time(0));
inline long long rnd(long long x) { return Random() % x; }
const long long INF = (long long)1e9 + 282;
const long long MOD = (long long)1e9 + 7;
const long double PI = acosl(-1.0);
const long long N = 3e5 + 10;
vector<vector<long long>> first, ff;
vector<vector<vector<long long>>> rs, cs;
pair<long long, long long> w[4][4];
char ccc[4] = {'A', 'T', 'G', 'C'};
void calcR(long long r, long long a, long long b, long long n, long long m) {
  for (long long i = 0; i < m; i++) {
    if (i % 2 == 0) {
      rs[r][a][b] += first[r][i] != a;
    } else {
      rs[r][a][b] += first[r][i] != b;
    }
  }
}
void calcC(long long c, long long a, long long b, long long n, long long m) {
  for (long long i = 0; i < n; i++) {
    if (i % 2 == 0) {
      cs[c][a][b] += first[i][c] != a;
    } else {
      cs[c][a][b] += first[i][c] != b;
    }
  }
}
pair<long long, pair<long long, long long>> goV(long long n, long long m) {
  pair<long long, pair<long long, long long>> ans = {INF, {-1, -1}};
  for (long long a = 0; a < 4; a++) {
    for (long long b = a + 1; b < 4; b++) {
      long long c = w[a][b].first, d = w[a][b].second;
      long long cur = 0;
      for (long long i = 0; i < m; i++) {
        if (i % 2 == 0) {
          cur += min(cs[i][a][b], cs[i][b][a]);
        } else {
          cur += min(cs[i][c][d], cs[i][d][c]);
        }
      }
      if (cur < ans.first) {
        ans = {cur, {a, b}};
      }
    }
  }
  return ans;
}
pair<long long, pair<long long, long long>> goH(long long n, long long m) {
  pair<long long, pair<long long, long long>> ans = {INF, {-1, -1}};
  for (long long a = 0; a < 4; a++) {
    for (long long b = a + 1; b < 4; b++) {
      long long c = w[a][b].first, d = w[a][b].second;
      long long cur = 0;
      for (long long i = 0; i < n; i++) {
        if (i % 2 == 0) {
          cur += min(rs[i][a][b], rs[i][b][a]);
        } else {
          cur += min(rs[i][c][d], rs[i][d][c]);
        }
      }
      if (cur < ans.first) {
        ans = {cur, {a, b}};
      }
    }
  }
  return ans;
}
void goAnsV(long long n, long long m, long long a, long long b) {
  long long c = w[a][b].first, d = w[a][b].second;
  for (long long i = 0; i < m; i++) {
    if (i % 2 == 0) {
      if (cs[i][a][b] < cs[i][b][a]) {
        for (long long j = 0; j < n; j++) {
          if (j % 2 == 0) {
            ff[j][i] = a;
          } else {
            ff[j][i] = b;
          }
        }
      } else {
        for (long long j = 0; j < n; j++) {
          if (j % 2 == 0) {
            ff[j][i] = b;
          } else {
            ff[j][i] = a;
          }
        }
      }
    } else {
      if (cs[i][c][d] < cs[i][d][c]) {
        for (long long j = 0; j < n; j++) {
          if (j % 2 == 0) {
            ff[j][i] = c;
          } else {
            ff[j][i] = d;
          }
        }
      } else {
        for (long long j = 0; j < n; j++) {
          if (j % 2 == 0) {
            ff[j][i] = d;
          } else {
            ff[j][i] = c;
          }
        }
      }
    }
  }
}
void goAnsH(long long n, long long m, long long a, long long b) {
  long long c = w[a][b].first, d = w[a][b].second;
  for (long long i = 0; i < n; i++) {
    if (i % 2 == 0) {
      if (rs[i][a][b] < rs[i][b][a]) {
        for (long long j = 0; j < m; j++) {
          if (j % 2 == 0) {
            ff[i][j] = a;
          } else {
            ff[i][j] = b;
          }
        }
      } else {
        for (long long j = 0; j < m; j++) {
          if (j % 2 == 0) {
            ff[i][j] = b;
          } else {
            ff[i][j] = a;
          }
        }
      }
    } else {
      if (rs[i][c][d] < rs[i][d][c]) {
        for (long long j = 0; j < m; j++) {
          if (j % 2 == 0) {
            ff[i][j] = c;
          } else {
            ff[i][j] = d;
          }
        }
      } else {
        for (long long j = 0; j < m; j++) {
          if (j % 2 == 0) {
            ff[i][j] = d;
          } else {
            ff[i][j] = c;
          }
        }
      }
    }
  }
}
void mane() {
  long long n, m;
  cin >> n >> m;
  first.resize(n, vector<long long>(m, 0));
  map<char, long long> mp;
  mp['A'] = 0;
  mp['T'] = 1;
  mp['G'] = 2;
  mp['C'] = 3;
  for (long long i = 0; i < 4; i++) {
    for (long long j = i + 1; j < 4; j++) {
      set<long long> st;
      for (long long k = 0; k < 4; k++) {
        st.insert(k);
      }
      st.erase(i);
      st.erase(j);
      w[i][j].first = *st.begin();
      st.erase(st.begin());
      w[i][j].second = *st.begin();
    }
  }
  for (long long i = 0; i < n; i++) {
    for (long long j = 0; j < m; j++) {
      char c;
      cin >> c;
      first[i][j] = mp[c];
    }
  }
  rs.resize(n, vector<vector<long long>>(4, vector<long long>(4, 0)));
  cs.resize(m, vector<vector<long long>>(4, vector<long long>(4, 0)));
  for (long long i = 0; i < n; i++) {
    for (long long a = 0; a < 4; a++) {
      for (long long b = 0; b < 4; b++) {
        if (a == b) {
          continue;
        }
        calcR(i, a, b, n, m);
      }
    }
  }
  for (long long i = 0; i < m; i++) {
    for (long long a = 0; a < 4; a++) {
      for (long long b = 0; b < 4; b++) {
        if (a == b) {
          continue;
        }
        calcC(i, a, b, n, m);
      }
    }
  }
  auto v = goV(n, m), h = goH(n, m);
  ff = first;
  if (v.first < h.first) {
    goAnsV(n, m, v.second.first, v.second.second);
  } else {
    goAnsH(n, m, h.second.first, h.second.second);
  }
  for (long long i = 0; i < n; i++) {
    for (long long j = 0; j < m; j++) {
      cout << ccc[ff[i][j]];
    }
    cout << "\n";
  }
}
int32_t main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cout.setf(ios_base::fixed, ios_base::floatfield);
  cout.precision(12);
  mane();
}
