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 MAXN = 300005;
const int INF = (int)1e9;
char base[] = {'A', 'C', 'G', 'T'};
vector<string> v;
char s[MAXN];
char aux[MAXN];
int n, m;
vector<char> r1[2];
vector<char> r2[2];
vector<char> c1[2];
vector<char> c2[2];
vector<vector<char> > best_row;
vector<vector<char> > best_col;
int mini_row = INF;
int mini_col = INF;
vector<vector<char> > aux_row[2];
vector<vector<char> > aux_col[2];
pair<int, int> calc_row(int row, vector<char>& a, vector<char>& b) {
  int va = 0;
  int vb = 0;
  for (int t = 0; t < m; t++) {
    if (v[row][t] != a[t]) va++;
    if (v[row][t] != b[t]) vb++;
  }
  if (va < vb) {
    return {0, va};
  }
  return {1, vb};
}
pair<int, int> calc_col(int col, vector<char>& a, vector<char>& b) {
  int va = 0;
  int vb = 0;
  for (int t = 0; t < n; t++) {
    if (v[t][col] != a[t]) va++;
    if (v[t][col] != b[t]) vb++;
  }
  if (va < vb) {
    return {0, va};
  }
  return {1, vb};
}
void solve_row(int i, int j, int k, int p) {
  for (int t = 0; t < m; t++) {
    if (t % 2 == 0) {
      r1[0][t] = base[i];
      r1[1][t] = base[j];
      r2[0][t] = base[k];
      r2[1][t] = base[p];
    } else {
      r1[0][t] = base[j];
      r1[1][t] = base[i];
      r2[0][t] = base[p];
      r2[1][t] = base[k];
    }
  }
  int v1 = 0;
  int v2 = 0;
  for (int t = 0; t < n; t++) {
    if (t % 2 == 0) {
      pair<int, int> score;
      score = calc_row(t, r1[0], r1[1]);
      if (score.first == 0) {
        aux_row[0].push_back(r1[0]);
      } else {
        aux_row[0].push_back(r1[1]);
      }
      v1 += score.second;
      score = calc_row(t, r2[0], r2[1]);
      if (score.first == 0) {
        aux_row[1].push_back(r2[0]);
      } else {
        aux_row[1].push_back(r2[1]);
      }
      v2 += score.second;
    } else {
      pair<int, int> score = calc_row(t, r2[0], r2[1]);
      if (score.first == 0) {
        aux_row[0].push_back(r2[0]);
      } else {
        aux_row[0].push_back(r2[1]);
      }
      v1 += score.second;
      score = calc_row(t, r1[0], r1[1]);
      if (score.first == 0) {
        aux_row[1].push_back(r1[0]);
      } else {
        aux_row[1].push_back(r1[1]);
      }
      v2 += score.second;
    }
  }
  if (v1 <= v2 && mini_row > v1) {
    mini_row = v1;
    best_row = aux_row[0];
  }
  if (v2 <= v1 && mini_row > v2) {
    mini_row = v2;
    best_row = aux_row[1];
  }
  for (int t = 0; t < 2; t++) {
    aux_row[t].clear();
  }
  return;
}
void solve_row() {
  for (int i = 0; i < 2; i++) {
    r1[i].resize(m);
    r2[i].resize(m);
  }
  for (int i = 0; i < 4; i++) {
    for (int j = 0; j < 4; j++) {
      for (int k = 0; k < 4; k++) {
        for (int p = 0; p < 4; p++) {
          if (i != j && i != k && i != p && j != k && j != p && k != p) {
            solve_row(i, j, k, p);
          }
        }
      }
    }
  }
  return;
}
void solve_col(int i, int j, int k, int p) {
  for (int t = 0; t < n; t++) {
    if (t % 2 == 0) {
      c1[0][t] = base[i];
      c1[1][t] = base[j];
      c2[0][t] = base[k];
      c2[1][t] = base[p];
    } else {
      c1[0][t] = base[j];
      c1[1][t] = base[i];
      c2[0][t] = base[p];
      c2[1][t] = base[k];
    }
  }
  int v1 = 0;
  int v2 = 0;
  for (int t = 0; t < m; t++) {
    if (t % 2 == 0) {
      pair<int, int> score = calc_col(t, c1[0], c1[1]);
      if (score.first == 0) {
        aux_col[0].push_back(c1[0]);
      } else {
        aux_col[0].push_back(c1[1]);
      }
      v1 += score.second;
      score = calc_col(t, c2[0], c2[1]);
      if (score.first == 0) {
        aux_col[1].push_back(c2[0]);
      } else {
        aux_col[1].push_back(c2[1]);
      }
      v2 += score.second;
    } else {
      pair<int, int> score = calc_col(t, c2[0], c2[1]);
      if (score.first == 0) {
        aux_col[0].push_back(c2[0]);
      } else {
        aux_col[0].push_back(c2[1]);
      }
      v1 += score.second;
      score = calc_col(t, c1[0], c1[1]);
      if (score.first == 0) {
        aux_col[1].push_back(c1[0]);
      } else {
        aux_col[1].push_back(c1[1]);
      }
      v2 += score.second;
    }
  }
  if (v1 <= v2 && mini_col > v1) {
    mini_col = v1;
    best_col = aux_col[0];
  }
  if (v2 <= v1 && mini_col > v2) {
    mini_col = v2;
    best_col = aux_col[1];
  }
  for (int t = 0; t < 2; t++) {
    aux_col[t].clear();
  }
  return;
}
void solve_col() {
  for (int i = 0; i < 2; i++) {
    c1[i].resize(n);
    c2[i].resize(n);
  }
  for (int i = 0; i < 4; i++) {
    for (int j = 0; j < 4; j++) {
      for (int k = 0; k < 4; k++) {
        for (int p = 0; p < 4; p++) {
          if (i != j && i != k && i != p && j != k && j != p && k != p) {
            solve_col(i, j, k, p);
          }
        }
      }
    }
  }
  return;
}
void print_col(void) {
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      printf("%c", best_col[j][i]);
    }
    printf("\n");
  }
  return;
}
void print_row(void) {
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      printf("%c", best_row[i][j]);
    }
    printf("\n");
  }
  return;
}
int main(void) {
  scanf(" %d %d", &n, &m);
  v.resize(n);
  for (int i = 0; i < n; i++) {
    scanf(" %s", aux);
    v[i] = string(aux);
  }
  solve_row();
  solve_col();
  if (mini_row < mini_col) {
    print_row();
  } else {
    print_col();
  }
  return 0;
}
