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;
const int MAX_N = 3e5 + 15, MOD = 1e9 + 7, inf = 1e9 + 7;
int n, m;
char A, B, C, D;
char c[] = {'A', 'G', 'C', 'T'};
vector<string> table, ans;
int ans1 = inf, ans2 = inf;
char A1, B1, C1, D1;
char A2, B2, C2, D2;
int calc1(char a, char b, char c, char d) {
  int sum = 0;
  for (int i = 0; i < n; i++) {
    if (i & 1) {
      int res1 = 0;
      int res2 = 0;
      for (int j = 0; j < m; j++) res1 += (table[i][j] != (j & 1 ? c : d));
      for (int j = 0; j < m; j++) res2 += (table[i][j] != (j & 1 ? d : c));
      sum += min(res1, res2);
    } else {
      int res1 = 0;
      int res2 = 0;
      for (int j = 0; j < m; j++) res1 += (table[i][j] != (j & 1 ? a : b));
      for (int j = 0; j < m; j++) res2 += (table[i][j] != (j & 1 ? b : a));
      sum += min(res1, res2);
    }
  }
  return sum;
}
int calc2(char a, char b, char c, char d) {
  int sum = 0;
  for (int i = 0; i < m; i++) {
    if (i & 1) {
      int res1 = 0;
      int res2 = 0;
      for (int j = 0; j < n; j++) res1 += (table[j][i] != (j & 1 ? c : d));
      for (int j = 0; j < n; j++) res2 += (table[j][i] != (j & 1 ? d : c));
      sum += min(res1, res2);
    } else {
      int res1 = 0;
      int res2 = 0;
      for (int j = 0; j < n; j++) res1 += (table[j][i] != (j & 1 ? a : b));
      for (int j = 0; j < n; j++) res2 += (table[j][i] != (j & 1 ? b : a));
      sum += min(res1, res2);
    }
  }
  return sum;
}
void upd1(char a, char b, char c, char d) {
  int res = calc1(a, b, c, d);
  if (res < ans1) {
    ans1 = res;
    A1 = a, B1 = b, C1 = c, D1 = d;
  }
}
void upd2(char a, char b, char c, char d) {
  int res = calc2(a, b, c, d);
  if (res < ans2) {
    ans2 = res;
    A2 = a, B2 = b, C2 = c, D2 = d;
  }
}
void build1(char a, char b, char c, char d) {
  for (int i = 0; i < n; i++) {
    if (i & 1) {
      int res1 = 0;
      int res2 = 0;
      for (int j = 0; j < m; j++) res1 += (table[i][j] != (j & 1 ? c : d));
      for (int j = 0; j < m; j++) res2 += (table[i][j] != (j & 1 ? d : c));
      string s;
      if (res1 < res2) {
        for (int j = 0; j < m; j++) s += (j & 1 ? c : d);
      } else {
        for (int j = 0; j < m; j++) s += (j & 1 ? d : c);
      }
      cout << s << "\n";
    } else {
      int res1 = 0;
      int res2 = 0;
      for (int j = 0; j < m; j++) res1 += (table[i][j] != (j & 1 ? a : b));
      for (int j = 0; j < m; j++) res2 += (table[i][j] != (j & 1 ? b : a));
      string s;
      if (res1 < res2) {
        for (int j = 0; j < m; j++) s += (j & 1 ? a : b);
      } else {
        for (int j = 0; j < m; j++) s += (j & 1 ? b : a);
      }
      cout << s << "\n";
    }
  }
}
void build2(char a, char b, char c, char d) {
  for (int i = 0; i < m; i++) {
    if (i & 1) {
      int res1 = 0;
      int res2 = 0;
      for (int j = 0; j < n; j++) res1 += (table[j][i] != (j & 1 ? c : d));
      for (int j = 0; j < n; j++) res2 += (table[j][i] != (j & 1 ? d : c));
      string s;
      if (res1 < res2) {
        for (int j = 0; j < n; j++) s += (j & 1 ? c : d);
      } else {
        for (int j = 0; j < n; j++) s += (j & 1 ? d : c);
      }
      ans.push_back(s);
    } else {
      int res1 = 0;
      int res2 = 0;
      for (int j = 0; j < n; j++) res1 += (table[j][i] != (j & 1 ? a : b));
      for (int j = 0; j < n; j++) res2 += (table[j][i] != (j & 1 ? b : a));
      string s;
      if (res1 < res2) {
        for (int j = 0; j < n; j++) s += (j & 1 ? a : b);
      } else {
        for (int j = 0; j < n; j++) s += (j & 1 ? b : a);
      }
      ans.push_back(s);
    }
  }
  for (int i = 0; i < n; i++) {
    string s;
    for (int j = 0; j < m; j++) s += ans[j][i];
    cout << s << "\n";
  }
}
int main() {
  ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  cin >> n >> m;
  for (int i = 0; i < n; i++) {
    string s;
    cin >> s;
    table.push_back(s);
  }
  int P1[] = {0, 1, 2, 3};
  do {
    upd1(c[P1[0]], c[P1[1]], c[P1[2]], c[P1[3]]);
  } while (next_permutation(P1, P1 + 4));
  int P2[] = {0, 1, 2, 3};
  do {
    upd2(c[P2[0]], c[P2[1]], c[P2[2]], c[P2[3]]);
  } while (next_permutation(P2, P2 + 4));
  if (ans1 < ans2)
    build1(A1, B1, C1, D1);
  else
    build2(A2, B2, C2, D2);
  return 0;
}
