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 lmt = 3e5;
vector<string> s, ans, fek;
int n, m, res = 0, cnt[2][26][lmt];
char ch[4];
void chek1(char a, char b, char c, char d) {
  int tot = 0;
  for (int i = 0; i < n; i++) {
    if (i % 2) {
      int mx1 = 0, mx2 = 0;
      for (int j = 0; j < m; j++) {
        if (j % 2) {
          if (s[i][j] == a)
            mx1++;
          else if (s[i][j] == b)
            mx2++;
        } else {
          if (s[i][j] == b)
            mx1++;
          else if (s[i][j] == a)
            mx2++;
        }
      }
      tot += max(mx2, mx1);
      if (mx1 > mx2) {
        for (int j = 0; j < m; j++) {
          if (j % 2)
            fek[i][j] = a;
          else
            fek[i][j] = b;
        }
      } else {
        for (int j = 0; j < m; j++) {
          if (j % 2)
            fek[i][j] = b;
          else
            fek[i][j] = a;
        }
      }
    } else {
      int mx1 = 0, mx2 = 0;
      for (int j = 0; j < m; j++) {
        if (j % 2) {
          if (s[i][j] == c)
            mx1++;
          else if (s[i][j] == d)
            mx2++;
        } else {
          if (s[i][j] == d)
            mx1++;
          else if (s[i][j] == c)
            mx2++;
        }
      }
      tot += max(mx2, mx1);
      if (mx1 > mx2) {
        for (int j = 0; j < m; j++) {
          if (j % 2)
            fek[i][j] = c;
          else
            fek[i][j] = d;
        }
      } else {
        for (int j = 0; j < m; j++) {
          if (j % 2)
            fek[i][j] = d;
          else
            fek[i][j] = c;
        }
      }
    }
  }
  if (tot > res) {
    res = tot;
    ans = fek;
  }
  return;
}
void chek2(char a, char b, char c, char d) {
  int tot = 0;
  for (int j = 0; j < m; j++) {
    if (j % 2) {
      int mx1 = 0, mx2 = 0;
      mx1 += cnt[0][a - 'A'][j] + cnt[1][b - 'A'][j];
      mx2 += cnt[0][b - 'A'][j] + cnt[1][a - 'A'][j];
      tot += max(mx2, mx1);
      if (mx1 > mx2) {
        fek[0][j] = a;
      } else {
        fek[0][j] = b;
      }
    } else {
      int mx1 = 0, mx2 = 0;
      mx1 += cnt[0][c - 'A'][j] + cnt[1][d - 'A'][j];
      mx2 += cnt[0][d - 'A'][j] + cnt[1][c - 'A'][j];
      tot += max(mx2, mx1);
      if (mx1 > mx2) {
        fek[0][j] = c;
      } else {
        fek[0][j] = d;
      }
    }
  }
  if (tot > res) {
    res = tot;
    for (int j = 0; j < m; j++) ans[0][j] = fek[0][j];
    for (int i = 1; i < n; i++) {
      for (int j = 0; j < m; j++) {
        if (ans[i - 1][j] == a)
          ans[i][j] = b;
        else if (ans[i - 1][j] == b)
          ans[i][j] = a;
        else if (ans[i - 1][j] == c)
          ans[i][j] = d;
        else
          ans[i][j] = c;
      }
    }
  }
  return;
}
int main() {
  ios_base::sync_with_stdio(false);
  ch[0] = 'A', ch[1] = 'C', ch[2] = 'G', ch[3] = 'T';
  cin >> n >> m;
  for (int i = 0; i < n; i++) {
    string t;
    cin >> t;
    ans.push_back(t);
    fek.push_back(t);
    s.push_back(t);
  }
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) cnt[i % 2][s[i][j] - 'A'][j]++;
  }
  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 (i == j || i == k || i == l || j == k || j == l || k == l)
            continue;
          chek1(ch[i], ch[j], ch[k], ch[l]);
          chek2(ch[i], ch[j], ch[k], ch[l]);
        }
      }
    }
  }
  cout << "\n";
  for (int i = 0; i < n; i++) {
    cout << ans[i] << "\n";
  }
  return 0;
}
