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;
int row[2][4][150000];
int col[2][4][150000];
int r, cc;
int go1() {
  int ret = 0;
  for (int a = 0; a < 4; a++) {
    for (int b = 0; b < 4; b++) {
      if (a == b) {
        continue;
      }
      int now = 0;
      vector<int> zz;
      for (int i = 0; i < 4; i++) {
        if (i != a && i != b) {
          zz.push_back(i);
        }
      }
      int c = zz[0];
      int d = zz[1];
      for (int i = 0; i < r; i += 2) {
        int here =
            max(row[0][a][i] + row[1][b][i], row[0][b][i] + row[1][a][i]);
        now += here;
      }
      for (int i = 1; i < r; i += 2) {
        int here =
            max(row[0][c][i] + row[1][d][i], row[0][d][i] + row[1][c][i]);
        now += here;
      }
      ret = max(ret, now);
    }
  }
  return ret;
}
void build1(int ret) {
  char ch[4] = {'A', 'G', 'C', 'T'};
  for (int a = 0; a < 4; a++) {
    for (int b = 0; b < 4; b++) {
      if (a == b) {
        continue;
      }
      int now = 0;
      vector<int> zz;
      for (int i = 0; i < 4; i++) {
        if (i != a && i != b) {
          zz.push_back(i);
        }
      }
      int c = zz[0];
      int d = zz[1];
      for (int i = 0; i < r; i += 2) {
        int here =
            max(row[0][a][i] + row[1][b][i], row[0][b][i] + row[1][a][i]);
        now += here;
      }
      for (int i = 1; i < r; i += 2) {
        int here =
            max(row[0][c][i] + row[1][d][i], row[0][d][i] + row[1][c][i]);
        now += here;
      }
      if (now == ret) {
        for (int i = 0; i < r; i++) {
          if (i % 2 == 1) {
            swap(a, c);
            swap(b, d);
          }
          if (row[0][a][i] + row[1][b][i] > row[0][b][i] + row[1][a][i]) {
            for (int j = 0; j < cc; j++) {
              if (j % 2 == 0) {
                cout << ch[a];
              } else {
                cout << ch[b];
              }
            }
          } else {
            for (int j = 0; j < cc; j++) {
              if (j % 2 == 0) {
                cout << ch[b];
              } else {
                cout << ch[a];
              }
            }
          }
          cout << endl;
          if (i % 2 == 1) {
            swap(a, c);
            swap(b, d);
          }
        }
        return;
      }
    }
  }
}
int go2() {
  int ret = 0;
  for (int a = 0; a < 4; a++) {
    for (int b = 0; b < 4; b++) {
      if (a == b) {
        continue;
      }
      int now = 0;
      vector<int> zz;
      for (int i = 0; i < 4; i++) {
        if (i != a && i != b) {
          zz.push_back(i);
        }
      }
      int c = zz[0];
      int d = zz[1];
      for (int i = 0; i < cc; i += 2) {
        int here =
            max(col[0][a][i] + col[1][b][i], col[0][b][i] + col[1][a][i]);
        now += here;
      }
      for (int i = 1; i < cc; i += 2) {
        int here =
            max(col[0][c][i] + col[1][d][i], col[0][d][i] + col[1][c][i]);
        now += here;
      }
      ret = max(ret, now);
    }
  }
  return ret;
}
void build2(int ret) {
  char ch[4] = {'A', 'G', 'C', 'T'};
  char ans[r][cc];
  for (int a = 0; a < 4; a++) {
    for (int b = 0; b < 4; b++) {
      if (a == b) {
        continue;
      }
      int now = 0;
      vector<int> zz;
      for (int i = 0; i < 4; i++) {
        if (i != a && i != b) {
          zz.push_back(i);
        }
      }
      int c = zz[0];
      int d = zz[1];
      for (int i = 0; i < cc; i += 2) {
        int here =
            max(col[0][a][i] + col[1][b][i], col[0][b][i] + col[1][a][i]);
        now += here;
      }
      for (int i = 1; i < cc; i += 2) {
        int here =
            max(col[0][c][i] + col[1][d][i], col[0][d][i] + col[1][c][i]);
        now += here;
      }
      if (now == ret) {
        for (int i = 0; i < cc; i++) {
          if (i % 2 == 1) {
            swap(a, c);
            swap(b, d);
          }
          if (col[0][a][i] + col[1][b][i] > col[0][b][i] + col[1][a][i]) {
            for (int j = 0; j < r; j++) {
              if (j % 2 == 0) {
                ans[j][i] = ch[a];
              } else {
                ans[j][i] = ch[b];
              }
            }
          } else {
            for (int j = 0; j < r; j++) {
              if (j % 2 == 0) {
                ans[j][i] = ch[b];
              } else {
                ans[j][i] = ch[a];
              }
            }
          }
          if (i % 2 == 1) {
            swap(a, c);
            swap(b, d);
          }
        }
        for (int i = 0; i < r; i++) {
          for (int j = 0; j < cc; j++) {
            cout << ans[i][j];
          }
          cout << endl;
        }
        return;
      }
    }
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cin >> r >> cc;
  int a[r][cc];
  for (int i = 0; i < r; i++) {
    string s;
    cin >> s;
    for (int j = 0; j < cc; j++) {
      if (s[j] == 'A') {
        a[i][j] = 0;
      } else if (s[j] == 'G') {
        a[i][j] = 1;
      } else if (s[j] == 'C') {
        a[i][j] = 2;
      } else {
        a[i][j] = 3;
      }
    }
  }
  for (int a = 0; a < 2; a++) {
    for (int b = 0; b < 4; b++) {
      for (int c = 0; c < 150000; c++) {
        row[a][b][c] = 0;
        col[a][b][c] = 0;
      }
    }
  }
  for (int i = 0; i < r; i++) {
    for (int j = 0; j < cc; j++) {
      row[j % 2][a[i][j]][i]++;
      col[i % 2][a[i][j]][j]++;
    }
  }
  int aa = go1();
  int bb = go2();
  if (aa >= bb) {
    build1(aa);
  } else {
    build2(bb);
  }
}
