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;
using ll = long long;
using vi = vector<int>;
using vl = vector<long long>;
using pii = pair<int, int>;
using vpii = vector<pair<int, int>>;
template <class T>
inline bool ckmin(T& a, T b) {
  return b < a ? a = b, 1 : 0;
}
template <class T>
inline bool ckmax(T& a, T b) {
  return b > a ? a = b, 1 : 0;
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const char nl = '\n';
const int mxN = 2e5 + 10;
const int MOD = 1e9 + 7;
const long long infLL = 1e18;
int n, m, bst = MOD;
vector<string> ans;
vector<string> G(n, "");
void runhoriz(char a, char c, char g, char t) {
  vector<string> cur(n);
  for (int i = (0); i < (n); i++) {
    if (i & 1) {
      for (int j = (0); j < (m); j++) {
        if (j & 1)
          cur[i] += a;
        else
          cur[i] += c;
      }
      int dif1 = 0, dif2 = 0;
      for (int j = (0); j < (m); j++) {
        if (cur[i][j] != G[i][j]) dif1++;
      }
      for (int j = (0); j < (m); j++) {
        if (j & 1)
          cur[i][j] = c;
        else
          cur[i][j] = a;
      }
      for (int j = (0); j < (m); j++) {
        if (cur[i][j] != G[i][j]) dif2++;
      }
      if (dif1 < dif2) {
        for (int j = (0); j < (m); j++) {
          if (j & 1)
            cur[i][j] = a;
          else
            cur[i][j] = c;
        }
      }
    } else {
      for (int j = (0); j < (m); j++) {
        if (j & 1)
          cur[i] += g;
        else
          cur[i] += t;
      }
      int dif1 = 0, dif2 = 0;
      for (int j = (0); j < (m); j++) {
        if (cur[i][j] != G[i][j]) dif1++;
      }
      for (int j = (0); j < (m); j++) {
        if (j & 1)
          cur[i][j] = t;
        else
          cur[i][j] = g;
      }
      for (int j = (0); j < (m); j++) {
        if (cur[i][j] != G[i][j]) dif2++;
      }
      if (dif1 < dif2) {
        for (int j = (0); j < (m); j++) {
          if (j & 1)
            cur[i][j] = g;
          else
            cur[i][j] = t;
        }
      }
    }
  }
  int dif = 0;
  for (int i = (0); i < (n); i++) {
    for (int j = (0); j < (m); j++) {
      if (cur[i][j] != G[i][j]) {
        dif++;
      }
    }
  }
  if (ckmin(bst, dif)) {
    ans = cur;
  }
}
void runvert(char a, char c, char g, char t) {
  vector<string> cur(n, string('.', m));
  for (int i = (0); i < (n); i++) cur[i].resize(m);
  for (int j = (0); j < (m); j++) {
    if (j & 1) {
      for (int i = (0); i < (n); i++) {
        if (i & 1)
          cur[i][j] = a;
        else
          cur[i][j] = c;
      }
      int dif1 = 0, dif2 = 0;
      for (int i = (0); i < (n); i++) {
        if (cur[i][j] != G[i][j]) dif1++;
      }
      for (int i = (0); i < (n); i++) {
        if (i & 1)
          cur[i][j] = c;
        else
          cur[i][j] = a;
      }
      for (int i = (0); i < (n); i++) {
        if (cur[i][j] != G[i][j]) dif2++;
      }
      if (dif1 < dif2) {
        for (int i = (0); i < (n); i++) {
          if (i & 1)
            cur[i][j] = a;
          else
            cur[i][j] = c;
        }
      }
    } else {
      for (int i = (0); i < (n); i++) {
        if (i & 1)
          cur[i][j] = g;
        else
          cur[i][j] = t;
      }
      int dif1 = 0, dif2 = 0;
      for (int i = (0); i < (n); i++) {
        if (cur[i][j] != G[i][j]) dif1++;
      }
      for (int i = (0); i < (n); i++) {
        if (i & 1)
          cur[i][j] = t;
        else
          cur[i][j] = g;
      }
      for (int i = (0); i < (n); i++) {
        if (cur[i][j] != G[i][j]) dif2++;
      }
      if (dif1 < dif2) {
        for (int i = (0); i < (n); i++) {
          if (i & 1)
            cur[i][j] = g;
          else
            cur[i][j] = t;
        }
      }
    }
  }
  int dif = 0;
  for (int i = (0); i < (n); i++) {
    for (int j = (0); j < (m); j++) {
      if (cur[i][j] != G[i][j]) {
        dif++;
      }
    }
  }
  if (ckmin(bst, dif)) {
    ans = cur;
  }
}
int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  char c[] = {'A', 'C', 'G', 'T'};
  cin >> n >> m;
  G.resize(n);
  for (int i = (0); i < (n); i++) {
    cin >> G[i];
  }
  for (int i = (0); i < (4); i++) {
    for (int j = (0); j < (4); j++) {
      for (int k = (0); k < (4); k++) {
        for (int l = (0); l < (4); l++) {
          if (l != i && l != j && l != k && k != j && k != i && j != i) {
            runhoriz(c[i], c[j], c[k], c[l]);
            runvert(c[i], c[j], c[k], c[l]);
          }
        }
      }
    }
  }
  for (int i = (0); i < (n); i++) {
    for (int j = (0); j < (m); j++) {
      cout << ans[i][j];
    }
    cout << nl;
  }
  return 0;
}
