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 = 100001;
const long long mod = 1e9 + 7;
int main() {
  int N, M;
  scanf("%d %d", &N, &M);
  char fin[N][M], ids[5] = "ACTG";
  int arr[N][M];
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < M; j++) {
      scanf(" %c", &fin[i][j]);
      if (fin[i][j] == 'A') {
        arr[i][j] = 0;
      } else if (fin[i][j] == 'C') {
        arr[i][j] = 1;
      } else if (fin[i][j] == 'T') {
        arr[i][j] = 2;
      } else {
        arr[i][j] = 3;
      }
    }
  }
  int assign[N / 2 + 1][4];
  int ans[N / 2 + 1][4];
  int ans1 = 2e9;
  for (int a = 0; a < 2; a++) {
    for (int c = 0; c < 2; c++) {
      for (int t = 0; t < 2; t++) {
        for (int g = 0; g < 2; g++) {
          if (a + c + t + g != 2) continue;
          vector<int> top, bot;
          if (a)
            top.push_back(0);
          else
            bot.push_back(0);
          if (c)
            top.push_back(1);
          else
            bot.push_back(1);
          if (t)
            top.push_back(2);
          else
            bot.push_back(2);
          if (g)
            top.push_back(3);
          else
            bot.push_back(3);
          int tot = 0;
          for (int i = 0; i < N / 2; i++) {
            int res = 2e9, cnt;
            for (int j = 0; j < 2; j++) {
              for (int k = 0; k < 2; k++) {
                cnt = 0;
                for (int l = 0; l < M; l++) {
                  if (arr[i * 2][l] != top[(l & 1) == j]) cnt++;
                  if (arr[i * 2 + 1][l] != bot[(l & 1) == k]) cnt++;
                }
                if (cnt < res) {
                  res = cnt;
                  assign[i][0] = top[j ^ 1];
                  assign[i][1] = top[j];
                  assign[i][2] = bot[k ^ 1];
                  assign[i][3] = bot[k];
                }
              }
            }
            tot += res;
          }
          if (N % 2) {
            int res = 2e9, cnt;
            for (int j = 0; j < 2; j++) {
              cnt = 0;
              for (int k = 0; k < M; k++) {
                if (arr[N - 1][k] != top[(k & 1) == j]) cnt++;
              }
              if (cnt < res) {
                res = cnt;
                assign[N / 2][0] = top[j ^ 1];
                assign[N / 2][1] = top[j];
              }
            }
            tot += res;
          }
          if (tot < ans1) {
            ans1 = tot;
            for (int j = 0; j < N / 2 + 1; j++) {
              for (int k = 0; k < 4; k++) {
                ans[j][k] = assign[j][k];
              }
            }
          }
        }
      }
    }
  }
  int assign2[M / 2 + 1][4];
  int ans2[M / 2 + 1][4];
  int ans3 = 2e9;
  for (int a = 0; a < 2; a++) {
    for (int c = 0; c < 2; c++) {
      for (int t = 0; t < 2; t++) {
        for (int g = 0; g < 2; g++) {
          if (a + c + t + g != 2) continue;
          vector<int> top, bot;
          if (a)
            top.push_back(0);
          else
            bot.push_back(0);
          if (c)
            top.push_back(1);
          else
            bot.push_back(1);
          if (t)
            top.push_back(2);
          else
            bot.push_back(2);
          if (g)
            top.push_back(3);
          else
            bot.push_back(3);
          int tot = 0;
          for (int i = 0; i < M / 2; i++) {
            int res = 2e9, cnt;
            for (int j = 0; j < 2; j++) {
              for (int k = 0; k < 2; k++) {
                cnt = 0;
                for (int l = 0; l < N; l++) {
                  if (arr[l][i * 2] != top[(l & 1) == j]) cnt++;
                  if (arr[l][i * 2 + 1] != bot[(l & 1) == k]) cnt++;
                }
                if (cnt < res) {
                  res = cnt;
                  assign2[i][0] = top[j ^ 1];
                  assign2[i][1] = top[j];
                  assign2[i][2] = bot[k ^ 1];
                  assign2[i][3] = bot[k];
                }
              }
            }
            tot += res;
          }
          if (M % 2) {
            int res = 2e9, cnt;
            for (int j = 0; j < 2; j++) {
              cnt = 0;
              for (int k = 0; k < N; k++) {
                if (arr[k][M - 1] != top[(k & 1) == j]) cnt++;
              }
              if (cnt < res) {
                res = cnt;
                assign2[M / 2][0] = top[j ^ 1];
                assign2[M / 2][1] = top[j];
              }
            }
            tot += res;
          }
          if (tot < ans3) {
            ans3 = tot;
            for (int j = 0; j < M / 2 + 1; j++) {
              for (int k = 0; k < 4; k++) {
                ans2[j][k] = assign2[j][k];
              }
            }
          }
        }
      }
    }
  }
  if (ans1 < ans3) {
    for (int i = 0; i < N / 2; i++) {
      for (int j = 0; j < M; j++) {
        fin[i * 2][j] = ids[ans[i][j & 1]];
        fin[i * 2 + 1][j] = ids[ans[i][(j & 1) + 2]];
      }
    }
    if (N % 2) {
      for (int j = 0; j < M; j++) {
        fin[N - 1][j] = ids[ans[N / 2][j & 1]];
      }
    }
  } else {
    for (int i = 0; i < M / 2; i++) {
      for (int j = 0; j < N; j++) {
        fin[j][i * 2] = ids[ans2[i][(j & 1)]];
        fin[j][i * 2 + 1] = ids[ans2[i][(j & 1) + 2]];
      }
    }
    if (M % 2) {
      for (int j = 0; j < N; j++) {
        fin[j][M - 1] = ids[ans2[M / 2][j & 1]];
      }
    }
  }
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < M; j++) {
      printf("%c", fin[i][j]);
    }
    printf("\n");
  }
}
