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 kMaxN = 300000;
string M1[kMaxN + 1];
string M2[kMaxN + 1];
string M3[kMaxN + 1];
int check_lines(string *M, int n, int m, char *s) {
  int ans = 0;
  for (int i = 0; i < n; ++i) {
    int v1 = 0;
    for (int j = 0; j < m; ++j) {
      if (j % 2 == 0) {
        if (M[i][j] != s[(i % 2) * 2]) ++v1;
      } else {
        if (M[i][j] != s[(i % 2) * 2 + 1]) ++v1;
      }
    }
    int v2 = 0;
    for (int j = 0; j < m; ++j) {
      if (j % 2 == 0) {
        if (M[i][j] != s[(i % 2) * 2 + 1]) ++v2;
      } else {
        if (M[i][j] != s[(i % 2) * 2]) ++v2;
      }
    }
    ans += min(v1, v2);
  }
  return ans;
}
void print(string *M, int n, int m, char *s) {
  for (int i = 0; i < n; ++i) {
    int v1 = 0;
    for (int j = 0; j < m; ++j) {
      if (j % 2 == 0) {
        if (M[i][j] != s[(i % 2) * 2]) ++v1;
      } else {
        if (M[i][j] != s[(i % 2) * 2 + 1]) ++v1;
      }
    }
    int v2 = 0;
    for (int j = 0; j < m; ++j) {
      if (j % 2 == 0) {
        if (M[i][j] != s[(i % 2) * 2 + 1]) ++v2;
      } else {
        if (M[i][j] != s[(i % 2) * 2]) ++v2;
      }
    }
    if (v1 < v2) {
      for (int j = 0; j < m; ++j) {
        if (j % 2 == 0) {
          M3[i].push_back(s[(i % 2) * 2]);
        } else
          M3[i].push_back(s[(i % 2) * 2 + 1]);
      }
    } else {
      for (int j = 0; j < m; ++j) {
        if (j % 2 == 0) {
          M3[i].push_back(s[(i % 2) * 2 + 1]);
        } else
          M3[i].push_back(s[(i % 2) * 2]);
      }
    }
  }
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n, m;
  cin >> n >> m;
  for (int i = 0; i < n; ++i) {
    cin >> M1[i];
    for (int j = 0; j < m; ++j) M2[j].push_back(M1[i][j]);
  }
  char s[] = "AGCT";
  int ans = numeric_limits<int>::max() / 2;
  char ans_s[] = "AGCT";
  int k = 1;
  do {
    int tmp = check_lines(M1, n, m, s);
    if (tmp < ans) {
      k = 1;
      for (int j = 0; j < 4; ++j) ans_s[j] = s[j];
      ans = tmp;
    }
    tmp = check_lines(M2, m, n, s);
    if (tmp < ans) {
      k = 2;
      for (int j = 0; j < 4; ++j) ans_s[j] = s[j];
      ans = tmp;
    }
  } while (next_permutation(s, s + 4));
  if (k == 1) {
    print(M1, n, m, ans_s);
    for (int i = 0; i < n; ++i) {
      cout << M3[i] << '\n';
    }
  } else {
    print(M2, m, n, ans_s);
    for (int j = 0; j < n; ++j) {
      for (int i = 0; i < m; ++i) cout << M3[i][j];
      cout << '\n';
    }
  }
  return 0;
}
