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;
using ll = long long;
using ii = pair<int, int>;
const int N = 100005;
int n, m;
vector<vector<char>> mat;
vector<vector<char>> ans;
vector<vector<char>> ans2;
ll qtd = 1e9;
int f(char i1, char j1, char i2, char j2, vector<vector<char>> &ansi = ans) {
  char x[2] = {i1, i2};
  char y[2] = {j1, j2};
  int aux = 0;
  for (int i = 0; i < n; i++) {
    int aux1 = 0, aux2 = 0;
    for (int j = 0; j < m; j++) {
      if (j & 1)
        aux1 += x[i & 1] != mat[i][j];
      else
        aux1 += y[i & 1] != mat[i][j];
    }
    for (int j = 0; j < m; j++) {
      if (!(j & 1))
        aux2 += x[i & 1] != mat[i][j];
      else
        aux2 += y[i & 1] != mat[i][j];
    }
    aux += min(aux1, aux2);
  }
  if (aux < qtd) {
    qtd = aux;
    for (int i = 0; i < n; i++) {
      int aux1 = 0, aux2 = 0;
      for (int j = 0; j < m; j++) {
        if (j & 1)
          aux1 += x[i & 1] != mat[i][j];
        else
          aux1 += y[i & 1] != mat[i][j];
      }
      for (int j = 0; j < m; j++) {
        if (!(j & 1))
          aux2 += x[i & 1] != mat[i][j];
        else
          aux2 += y[i & 1] != mat[i][j];
      }
      if (aux1 < aux2) {
        for (int j = 0; j < m; j++) {
          if (j & 1)
            ansi[i][j] = x[i & 1];
          else
            ansi[i][j] = y[i & 1];
        }
      } else {
        for (int j = 0; j < m; j++) {
          if (!(j & 1))
            ansi[i][j] = x[i & 1];
          else
            ansi[i][j] = y[i & 1];
        }
      }
    }
    return 1;
  }
  return 0;
}
vector<vector<char>> transp(vector<vector<char>> &mat) {
  vector<vector<char>> ret = vector<vector<char>>(m, vector<char>(n + 5));
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      ret[j][i] = mat[i][j];
    }
  }
  return ret;
}
int main() {
  scanf("%d %d", &n, &m);
  mat = vector<vector<char>>(n, vector<char>(m + 5));
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      scanf(" %c", &mat[i][j]);
    }
  }
  vector<char> v = {'A', 'C', 'G', 'T'};
  ans = vector<vector<char>>(n, vector<char>(m + 5));
  ans2 = vector<vector<char>>(m, vector<char>(n + 5));
  for (int i = 0; i < 4; i++) {
    for (int j = i + 1; j < 4; j++) {
      for (int i2 = 0; i2 < 4; i2++) {
        for (int j2 = i2 + 1; j2 < 4; j2++) {
          if (i != i2 && i != j2 && j != j2 && j != i2) {
            f(v[i], v[j], v[i2], v[j2]);
          }
        }
      }
    }
  }
  mat = transp(mat);
  swap(n, m);
  bool tp = 0;
  for (int i = 0; i < 4; i++) {
    for (int j = i + 1; j < 4; j++) {
      for (int i2 = 0; i2 < 4; i2++) {
        for (int j2 = i2 + 1; j2 < 4; j2++) {
          if (i != i2 && i != j2 && j != j2 && j != i2) {
            tp |= f(v[i], v[j], v[i2], v[j2], ans2);
          }
        }
      }
    }
  }
  if (tp) {
    ans = transp(ans2);
  }
  swap(n, m);
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      printf("%c", ans[i][j]);
    }
    printf("\n");
  }
  return 0;
}
