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;
long long best = 9223372036854775807;
long long n, m;
void horizontal(vector<vector<char> > &tab, vector<vector<char> > &rep, char a,
                char b, char c, char d) {
  vector<vector<char> > tempo(n, vector<char>(m));
  long long tot = 0;
  for (long long i = 0; i < n; i++) {
    if (tot >= best) return;
    long long da = 0;
    long long db = 0;
    if (i % 2 == 0) {
      for (long long j = 0; j < m; j++) {
        if (j % 2 == 0 && tab[i][j] != a)
          da++;
        else if (j % 2 == 1 && tab[i][j] != b) {
          da++;
        }
        if (j % 2 == 0 && tab[i][j] != b)
          db++;
        else if (j % 2 == 1 && tab[i][j] != a) {
          db++;
        }
      }
    } else {
      for (long long j = 0; j < m; j++) {
        if (j % 2 == 0 && tab[i][j] != c)
          da++;
        else if (j % 2 == 1 && tab[i][j] != d) {
          da++;
        }
        if (j % 2 == 0 && tab[i][j] != d)
          db++;
        else if (j % 2 == 1 && tab[i][j] != c) {
          db++;
        }
      }
    }
    if (da > db) {
      tot += db;
      if (i % 2 == 0) {
        for (long long j = 0; j < m; j++) {
          if (j % 2 == 0)
            tempo[i][j] = b;
          else
            tempo[i][j] = a;
        }
      } else {
        for (long long j = 0; j < m; j++) {
          if (j % 2 == 0)
            tempo[i][j] = d;
          else
            tempo[i][j] = c;
        }
      }
    } else {
      tot += da;
      if (i % 2 == 0) {
        for (long long j = 0; j < m; j++) {
          if (j % 2 == 0)
            tempo[i][j] = a;
          else
            tempo[i][j] = b;
        }
      } else {
        for (long long j = 0; j < m; j++) {
          if (j % 2 == 0)
            tempo[i][j] = c;
          else
            tempo[i][j] = d;
        }
      }
    }
  }
  if (tot < best) {
    best = tot;
    rep = tempo;
  }
}
void vertical(vector<vector<char> > &tab, vector<vector<char> > &rep, char a,
              char b, char c, char d) {
  vector<vector<char> > tempo(n, vector<char>(m));
  long long tot = 0;
  for (long long j = 0; j < m; j++) {
    if (tot >= best) return;
    long long da = 0;
    long long db = 0;
    if (j % 2 == 0) {
      for (long long i = 0; i < n; i++) {
        if (i % 2 == 0 && tab[i][j] != a)
          da++;
        else if (i % 2 == 1 && tab[i][j] != b) {
          da++;
        }
        if (i % 2 == 0 && tab[i][j] != b)
          db++;
        else if (i % 2 == 1 && tab[i][j] != a) {
          db++;
        }
      }
    } else {
      for (long long i = 0; i < n; i++) {
        if (i % 2 == 0 && tab[i][j] != c)
          da++;
        else if (i % 2 == 1 && tab[i][j] != d) {
          da++;
        }
        if (i % 2 == 0 && tab[i][j] != d)
          db++;
        else if (i % 2 == 1 && tab[i][j] != c) {
          db++;
        }
      }
    }
    if (da > db) {
      tot += db;
      if (j % 2 == 0) {
        for (long long i = 0; i < n; i++) {
          if (i % 2 == 0)
            tempo[i][j] = b;
          else
            tempo[i][j] = a;
        }
      } else {
        for (long long i = 0; i < n; i++) {
          if (i % 2 == 0)
            tempo[i][j] = d;
          else
            tempo[i][j] = c;
        }
      }
    } else {
      tot += da;
      if (j % 2 == 0) {
        for (long long i = 0; i < n; i++) {
          if (i % 2 == 0)
            tempo[i][j] = a;
          else
            tempo[i][j] = b;
        }
      } else {
        for (long long i = 0; i < n; i++) {
          if (i % 2 == 0)
            tempo[i][j] = c;
          else
            tempo[i][j] = d;
        }
      }
    }
  }
  if (tot < best) {
    best = tot;
    rep = tempo;
  }
}
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cin >> n >> m;
  vector<vector<char> > tab(n, vector<char>(m));
  for (long long i = 0; i < n; i++) {
    for (long long j = 0; j < m; j++) {
      cin >> tab[i][j];
    }
  }
  vector<vector<char> > ans(n, vector<char>(m));
  vector<char> liste(0);
  liste.push_back('A');
  liste.push_back('C');
  liste.push_back('G');
  liste.push_back('T');
  liste.push_back('G');
  liste.push_back('T');
  liste.push_back('A');
  liste.push_back('C');
  liste.push_back('A');
  liste.push_back('G');
  liste.push_back('C');
  liste.push_back('T');
  liste.push_back('C');
  liste.push_back('T');
  liste.push_back('A');
  liste.push_back('G');
  liste.push_back('A');
  liste.push_back('T');
  liste.push_back('C');
  liste.push_back('G');
  liste.push_back('C');
  liste.push_back('G');
  liste.push_back('A');
  liste.push_back('T');
  for (long long i = 0; i < liste.size(); i += 4) {
    horizontal(tab, ans, liste[i + 0], liste[i + 1], liste[i + 2],
               liste[i + 3]);
    vertical(tab, ans, liste[i + 0], liste[i + 1], liste[i + 2], liste[i + 3]);
  }
  for (long long i = 0; i < n; i++) {
    for (long long j = 0; j < m; j++) {
      cout << ans[i][j];
    }
    cout << endl;
  }
}
