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;
inline int read();
const int M = 300016, MOD = 1000000007;
int n, m, ans;
string save[M];
string output[M];
const char tpch[6][2] = {{'A', 'C'}, {'A', 'G'}, {'A', 'T'},
                         {'C', 'G'}, {'C', 'T'}, {'G', 'T'}};
void modify(int arc, int tp) {
  if (arc == 0) {
    for (int row = 0; row < n; ++row) {
      tp = 5 - tp;
      char c1 = tpch[tp][0], c2 = tpch[tp][1];
      int res1 = 0, res2 = 0;
      for (int c = 0; c < m; ++c) {
        char ch = save[row][c];
        if (c & 1) {
          if (ch != c1) ++res1;
          if (ch != c2) ++res2;
        } else {
          if (ch != c1) ++res2;
          if (ch != c2) ++res1;
        }
      }
      if (res1 < res2) {
        for (int c = 0; c < m; ++c) {
          if (c & 1)
            output[row][c] = c1;
          else
            output[row][c] = c2;
        }
      } else {
        for (int c = 0; c < m; ++c) {
          if (c & 1)
            output[row][c] = c2;
          else
            output[row][c] = c1;
        }
      }
    }
  } else {
    for (int col = 0; col < m; ++col) {
      tp = 5 - tp;
      char c1 = tpch[tp][0], c2 = tpch[tp][1];
      int res1 = 0, res2 = 0;
      for (int r = 0; r < n; ++r) {
        char ch = save[r][col];
        if (r & 1) {
          if (ch != c1) ++res1;
          if (ch != c2) ++res2;
        } else {
          if (ch != c1) ++res2;
          if (ch != c2) ++res1;
        }
      }
      if (res1 < res2) {
        for (int r = 0; r < n; ++r) {
          if (r & 1)
            output[r][col] = c1;
          else
            output[r][col] = c2;
        }
      } else {
        for (int r = 0; r < n; ++r) {
          if (r & 1)
            output[r][col] = c2;
          else
            output[r][col] = c1;
        }
      }
    }
  }
}
int calrow(int row, int tp) {
  char c1 = tpch[tp][0], c2 = tpch[tp][1];
  int res1 = 0, res2 = 0;
  for (int c = 0; c < m; ++c) {
    char ch = save[row][c];
    if (c & 1) {
      if (ch != c1) ++res1;
      if (ch != c2) ++res2;
    } else {
      if (ch != c1) ++res2;
      if (ch != c2) ++res1;
    }
  }
  return min(res1, res2);
}
int calcol(int col, int tp) {
  char c1 = tpch[tp][0], c2 = tpch[tp][1];
  int res1 = 0, res2 = 0;
  for (int r = 0; r < n; ++r) {
    char ch = save[r][col];
    if (r & 1) {
      if (ch != c1) ++res1;
      if (ch != c2) ++res2;
    } else {
      if (ch != c1) ++res2;
      if (ch != c2) ++res1;
    }
  }
  return min(res1, res2);
}
int save_row[M][6];
int save_col[M][6];
int main(void) {
  n = read(), m = read(), ans = INT_MAX;
  for (int i = 0; i < n; ++i) cin >> save[i];
  for (int i = 0; i < n; ++i) {
    for (int tp = 0; tp < 6; ++tp) {
      save_row[i][tp] = calrow(i, tp);
    }
  }
  for (int i = 0; i < m; ++i) {
    for (int tp = 0; tp < 6; ++tp) {
      save_col[i][tp] = calcol(i, tp);
    }
  }
  int atp = -1, arc = -1;
  for (int tp = 0; tp < 6; ++tp) {
    int tmp = 0;
    for (int r = 0; r < n; ++r) {
      if (r & 1)
        tmp += save_row[r][tp];
      else
        tmp += save_row[r][5 - tp];
    }
    if (tmp < ans) {
      ans = tmp;
      atp = tp;
      arc = 0;
    }
    tmp = 0;
    for (int c = 0; c < m; ++c) {
      if (c & 1)
        tmp += save_col[c][tp];
      else
        tmp += save_col[c][5 - tp];
    }
    if (tmp < ans) {
      ans = tmp;
      atp = tp;
      arc = 1;
    }
  }
  for (int i = 0; i < n; ++i) output[i] = save[i];
  modify(arc, atp);
  for (int i = 0; i < n; ++i) cout << output[i] << endl;
  return 0;
}
inline int read() {
  int x = 0, f = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return x * f;
}
