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;
char **a;
char **sol;
int sol1(int n, int m, char c1, char c2, char c3, char c4) {
  int ans = 0;
  for (int i = 1; i <= n; ++i) {
    int a1 = 0, a2 = 0;
    if (i % 2) {
      for (int j = 1; j <= m; ++j)
        if (j % 2) {
          if (a[i][j] != c1) a1++;
          if (a[i][j] != c2) a2++;
        } else {
          if (a[i][j] != c2) a1++;
          if (a[i][j] != c1) a2++;
        }
    } else {
      for (int j = 1; j <= m; ++j)
        if (j % 2) {
          if (a[i][j] != c3) a1++;
          if (a[i][j] != c4) a2++;
        } else {
          if (a[i][j] != c4) a1++;
          if (a[i][j] != c3) a2++;
        }
    }
    ans += min(a1, a2);
  }
  return ans;
}
int sol2(int n, int m, char c1, char c2, char c3, char c4) {
  int ans = 0;
  for (int j = 1; j <= m; ++j) {
    int a1 = 0, a2 = 0;
    if (j % 2) {
      for (int i = 1; i <= n; ++i)
        if (i % 2) {
          if (a[i][j] != c1) a1++;
          if (a[i][j] != c2) a2++;
        } else {
          if (a[i][j] != c2) a1++;
          if (a[i][j] != c1) a2++;
        }
    } else {
      for (int i = 1; i <= n; ++i)
        if (i % 2) {
          if (a[i][j] != c3) a1++;
          if (a[i][j] != c4) a2++;
        } else {
          if (a[i][j] != c4) a1++;
          if (a[i][j] != c3) a2++;
        }
    }
    ans += min(a1, a2);
  }
  return ans;
}
void get1(int n, int m, char c1, char c2, char c3, char c4) {
  for (int i = 1; i <= n; ++i) {
    int a1 = 0, a2 = 0;
    if (i % 2) {
      for (int j = 1; j <= m; ++j)
        if (j % 2) {
          if (a[i][j] != c1) a1++;
          if (a[i][j] != c2) a2++;
        } else {
          if (a[i][j] != c2)
            a1++;
          else
            a2++;
        }
      if (a1 > a2) swap(c1, c2);
      for (int j = 1; j <= m; ++j)
        if (j % 2 == 1)
          sol[i][j] = c1;
        else
          sol[i][j] = c2;
    } else {
      for (int j = 1; j <= m; ++j)
        if (j % 2) {
          if (a[i][j] != c3) a1++;
          if (a[i][j] != c4) a2++;
        } else {
          if (a[i][j] != c4) a1++;
          if (a[i][j] != c3) a2++;
        }
      if (a1 > a2) swap(c3, c4);
      for (int j = 1; j <= m; ++j)
        if (j % 2 == 1)
          sol[i][j] = c3;
        else
          sol[i][j] = c4;
    }
  }
}
void get2(int n, int m, char c1, char c2, char c3, char c4) {
  for (int j = 1; j <= m; ++j) {
    int a1 = 0, a2 = 0;
    if (j % 2) {
      for (int i = 1; i <= n; ++i)
        if (i % 2) {
          if (a[i][j] != c1) a1++;
          if (a[i][j] != c2) a2++;
        } else {
          if (a[i][j] != c2) a1++;
          if (a[i][j] != c1) a2++;
        }
      if (a1 > a2) swap(c1, c2);
      for (int i = 1; i <= n; ++i)
        if (i % 2 == 1)
          sol[i][j] = c1;
        else
          sol[i][j] = c2;
    } else {
      for (int i = 1; i <= n; ++i)
        if (i % 2) {
          if (a[i][j] != c3) a1++;
          if (a[i][j] != c4) a2++;
        } else {
          if (a[i][j] != c4) a1++;
          if (a[i][j] != c3) a2++;
        }
      if (a1 > a2) swap(c3, c4);
      for (int i = 1; i <= n; ++i)
        if (i % 2 == 1)
          sol[i][j] = c3;
        else
          sol[i][j] = c4;
    }
  }
}
int main() {
  int n, m;
  scanf("%d%d ", &n, &m);
  a = new char *[n + 5];
  sol = new char *[n + 5];
  for (int i = 1; i <= n; ++i) {
    a[i] = new char[m + 5];
    sol[i] = new char[m + 5];
  }
  for (int i = 1; i <= n; ++i) scanf("%s", a[i] + 1);
  int m1 = sol1(n, m, 'A', 'C', 'T', 'G');
  int m2 = sol1(n, m, 'A', 'G', 'C', 'T');
  int m3 = sol1(n, m, 'C', 'G', 'A', 'T');
  int m4 = sol1(n, m, 'C', 'T', 'A', 'G');
  int m5 = sol1(n, m, 'A', 'T', 'C', 'G');
  int m6 = sol1(n, m, 'G', 'T', 'A', 'C');
  int m7 = sol2(n, m, 'A', 'C', 'T', 'G');
  int m8 = sol2(n, m, 'A', 'G', 'C', 'T');
  int m9 = sol2(n, m, 'C', 'G', 'A', 'T');
  int m10 = sol2(n, m, 'C', 'T', 'A', 'G');
  int m11 = sol2(n, m, 'A', 'T', 'C', 'G');
  int m12 = sol2(n, m, 'G', 'T', 'A', 'C');
  int k1 = min(min(min(min(min(m1, m2), m3), m4), m5), m6);
  int k2 = min(min(min(min(min(m7, m8), m9), m10), m11), m12);
  int k = min(k1, k2);
  if (m1 == k)
    get1(n, m, 'A', 'C', 'T', 'G');
  else if (m2 == k)
    get1(n, m, 'A', 'G', 'C', 'T');
  else if (m3 == k)
    get1(n, m, 'C', 'G', 'A', 'T');
  else if (m4 == k)
    get1(n, m, 'C', 'T', 'A', 'G');
  else if (m5 == k)
    get1(n, m, 'A', 'T', 'C', 'G');
  else if (m6 == k)
    get1(n, m, 'G', 'T', 'A', 'C');
  else if (m7 == k)
    get2(n, m, 'A', 'C', 'T', 'G');
  else if (m8 == k)
    get2(n, m, 'A', 'G', 'C', 'T');
  else if (m9 == k)
    get2(n, m, 'C', 'G', 'A', 'T');
  else if (m10 == k)
    get2(n, m, 'C', 'T', 'A', 'G');
  else if (m11 == k)
    get2(n, m, 'A', 'T', 'C', 'G');
  else
    get2(n, m, 'G', 'T', 'A', 'C');
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= m; ++j) printf("%c", sol[i][j]);
    printf("\n");
  }
  return 0;
}
