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;
template <class S, class T>
pair<S, T> operator+(const pair<S, T> &s, const pair<S, T> &t) {
  return pair<S, T>(s.first + t.first, s.second + t.second);
}
template <class S, class T>
pair<S, T> operator-(const pair<S, T> &s, const pair<S, T> &t) {
  return pair<S, T>(s.first - t.first, s.second - t.second);
}
template <class S, class T>
ostream &operator<<(ostream &os, pair<S, T> p) {
  os << "(" << p.first << ", " << p.second << ")";
  return os;
}
template <class T>
bool chmax(T &a, const T &b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}
template <class T>
bool chmin(T &a, const T &b) {
  if (a > b) {
    a = b;
    return 1;
  }
  return 0;
}
const long long inf = 1000000001;
const long long INF = 1e18;
const long long MOD = 1000000007;
const double pi = 3.14159265358979323846;
int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
int dx2[8] = {1, 1, 0, -1, -1, -1, 0, 1}, dy2[8] = {0, 1, 1, 1, 0, -1, -1, -1};
vector<string> rotate(vector<string> s) {
  int h = s.size(), w = s[0].size();
  vector<string> t(w, string(h, '?'));
  for (int i = 0; i < (h); i++) {
    for (int j = 0; j < (w); j++) {
      t[j][i] = s[i][j];
    }
  }
  return t;
}
long long best = INF;
int bestm = -1;
int besti = -1;
long long solve(vector<string> s, int m, string p1, string p2) {
  int h = s.size(), w = s[0].size();
  long long sum = 0;
  for (int i = 0; i < (h); i++) {
    string p;
    if (i % 2 == 0) {
      p = p1;
    } else {
      p = p2;
    }
    int temp1 = 0, temp2 = 0;
    for (int j = 0; j < (w); j++) {
      if (j % 2 == 0) {
        if (s[i][j] != p[0]) temp1++;
        if (s[i][j] != p[1]) temp2++;
      } else {
        if (s[i][j] != p[1]) temp1++;
        if (s[i][j] != p[0]) temp2++;
      }
    }
    sum += min(temp1, temp2);
  }
  return sum;
}
vector<string> solve2(vector<string> s, int m, string p1, string p2) {
  int h = s.size(), w = s[0].size();
  long long sum = 0;
  for (int i = 0; i < (h); i++) {
    string p;
    if (i % 2 == 0) {
      p = p1;
    } else {
      p = p2;
    }
    int temp1 = 0, temp2 = 0;
    for (int j = 0; j < (w); j++) {
      if (j % 2 == 0) {
        if (s[i][j] != p[0]) temp1++;
        if (s[i][j] != p[1]) temp2++;
      } else {
        if (s[i][j] != p[1]) temp1++;
        if (s[i][j] != p[0]) temp2++;
      }
    }
    if (temp1 < temp2) {
      for (int j = 0; j < (w); j++) {
        if (j % 2 == 0) {
          s[i][j] = p[0];
        } else {
          s[i][j] = p[1];
        }
      }
    } else {
      for (int j = 0; j < (w); j++) {
        if (j % 2 == 0) {
          s[i][j] = p[1];
        } else {
          s[i][j] = p[0];
        }
      }
    }
  }
  return s;
}
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  ;
  int h, w;
  cin >> h >> w;
  vector<string> s(h);
  for (int i = 0; i < (h); i++) {
    cin >> s[i];
  }
  vector<string> i2s1 = {"AG", "AC", "AT", "GC", "GT", "CT"};
  vector<string> i2s2 = {"CT", "GT", "GC", "AT", "AC", "AG"};
  if (min(h, w) == 2) {
    bool flag = false;
    if (w < h) {
      swap(h, w);
      s = rotate(s);
      flag = true;
    }
    long long mi = INF;
    int idx = -1;
    for (int i = 0; i < (6); i++) {
      string p1 = i2s1[i], p2 = i2s2[i];
      long long sum = 0;
      for (int j = 0; j < (w); j++) {
        long long temp1 = 0, temp2 = 0;
        if (j % 2 == 0) {
          if (s[0][j] != p1[0]) temp1++;
          if (s[1][j] != p1[1]) temp1++;
          if (s[0][j] != p1[1]) temp2++;
          if (s[1][j] != p1[0]) temp2++;
        } else {
          if (s[0][j] != p2[0]) temp1++;
          if (s[1][j] != p2[1]) temp1++;
          if (s[0][j] != p2[1]) temp2++;
          if (s[1][j] != p2[0]) temp2++;
        }
        sum += min(temp1, temp2);
      }
      if (sum < mi) {
        mi = sum;
        idx = i;
      }
    }
    string p1 = i2s1[idx], p2 = i2s2[idx];
    long long sum = 0;
    for (int j = 0; j < (w); j++) {
      long long temp1 = 0, temp2 = 0;
      if (j % 2 == 0) {
        if (s[0][j] != p1[0]) temp1++;
        if (s[1][j] != p1[1]) temp1++;
        if (s[0][j] != p1[1]) temp2++;
        if (s[1][j] != p1[0]) temp2++;
        if (temp1 < temp2) {
          s[0][j] = p1[0];
          s[1][j] = p1[1];
        } else {
          s[0][j] = p1[1];
          s[1][j] = p1[0];
        }
      } else {
        if (s[0][j] != p2[0]) temp1++;
        if (s[1][j] != p2[1]) temp1++;
        if (s[0][j] != p2[1]) temp2++;
        if (s[1][j] != p2[0]) temp2++;
        if (temp1 < temp2) {
          s[0][j] = p2[0];
          s[1][j] = p2[1];
        } else {
          s[0][j] = p2[1];
          s[1][j] = p2[0];
        }
      }
    }
    if (flag) {
      s = rotate(s);
      swap(h, w);
    }
    for (int i = 0; i < (h); i++) {
      cout << s[i] << endl;
    }
    return 0;
  }
  for (int i = 0; i < (6); i++) {
    string p1 = i2s1[i], p2 = i2s2[i];
    long long res = solve(s, 0, p1, p2);
    if (res < best) {
      best = res;
      bestm = 0;
      besti = i;
    }
  }
  s = rotate(s);
  for (int i = 0; i < (6); i++) {
    string p1 = i2s1[i], p2 = i2s2[i];
    long long res = solve(s, 1, p1, p2);
    if (res < best) {
      best = res;
      bestm = 1;
      besti = i;
    }
  }
  string p1 = i2s1[besti], p2 = i2s2[besti];
  if (bestm == 0) {
    s = rotate(s);
  }
  s = solve2(s, bestm, p1, p2);
  if (bestm == 1) {
    s = rotate(s);
  }
  for (int i = 0; i < (s.size()); i++) {
    cout << s[i] << endl;
  }
}
