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.
import java.util.*;
import java.io.*;
import java.lang.*;
import java.math.*;
public class B {
    public static int n;
    public static int m;
    public static char[][] grid;
    public static String[] grid_s;
    public static void main(String[] args) throws Exception {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        // Scanner scan = new Scanner(System.in);
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        // int n = Integer.parseInt(bf.readLine());
        StringTokenizer st = new StringTokenizer(bf.readLine());
        // int[] a = new int[n]; for(int i=0; i<n; i++) a[i] = Integer.parseInt(st.nextToken());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        grid = new char[n][m];
        grid_s = new String[n];
        for(int i=0; i<n; i++) {
          String s = bf.readLine();
          grid_s[i] = s;
          for(int j=0; j<m; j++) grid[i][j] = s.charAt(j);
        }
        String[] pairs_2 = {"CT", "CA", "CG", "TA", "TG", "AG"};
        String[] pairs = {"TC", "AC", "GC", "AT", "GT", "GA"};
        String[] n_pairs_2 = {"AG", "TG", "AT", "GC", "AC", "CT"};
        String[] n_pairs = {"GA", "GT", "TA", "CG", "CA", "TC"};

        int type = -1;
        int index = -1;

        int ans = n*m+1;

        for(int c=0; c<6; c++) {
          int cur_ans = 0;
          for(int i=0; i<n; i++) {
            if((i%2) == 1) {
            int v1 = compare(grid_s[i], repeat(pairs[c], m));
            int v2 = compare(grid_s[i], repeat(pairs_2[c], m));
            cur_ans += Math.min(v1, v2);
            }
            else {
              int v1 = compare(grid_s[i], repeat(n_pairs[c], m));
              int v2 = compare(grid_s[i], repeat(n_pairs_2[c], m));
              cur_ans += Math.min(v1, v2);
            }
          }
          if(cur_ans < ans) {
            ans = cur_ans;
            type = 1;
            index = c;
          }
        }

        String[] pairs_4 = {"CT", "CA", "CG", "TC", "AC", "GC", "CT", "CA", "CG", "TC", "AC", "GC"};
        String[] pairs_3 = {"AG", "TG", "TA", "GA", "GT", "TA", "GA", "GT", "AT", "AG", "TG", "AT"};
        //
        for(int c=0; c<12; c++) {
          int cur_ans = 0;
          for(int j=0; j<m; j+=2) {
            int v1 = 0;
            for(int i=0; i<n; i+=2) {
              if(valid(i,j) && (grid[i][j] != pairs_3[c].charAt(0))) v1++;
              if(valid(i+1,j) && (grid[i+1][j] != pairs_4[c].charAt(0))) v1++;
              if(valid(i,j+1) && (grid[i][j+1] != pairs_3[c].charAt(1))) v1++;
              if(valid(i+1,j+1) && (grid[i+1][j+1] != pairs_4[c].charAt(1))) v1++;
            }
            int v2 = 0;
            for(int i=0; i<n; i+=2) {
              if(valid(i,j) && (grid[i][j] != pairs_4[c].charAt(0))) v2++;
              if(valid(i+1,j) && (grid[i+1][j] != pairs_3[c].charAt(0))) v2++;
              if(valid(i,j+1) && (grid[i][j+1] != pairs_4[c].charAt(1))) v2++;
              if(valid(i+1,j+1) && (grid[i+1][j+1] != pairs_3[c].charAt(1))) v2++;
            }
            int v3 = 0;
            for(int i=0; i<n; i+=2) {
              if(valid(i,j) && (grid[i][j] != pairs_3[c].charAt(0))) v3++;
              if(valid(i+1,j) && (grid[i+1][j] != pairs_4[c].charAt(0))) v3++;
              if(valid(i,j+1) && (grid[i][j+1] != pairs_4[c].charAt(1))) v3++;
              if(valid(i+1,j+1) && (grid[i+1][j+1] != pairs_3[c].charAt(1))) v3++;
            }
            int v4 = 0;
            for(int i=0; i<n; i+=2) {
              if(valid(i,j) && (grid[i][j] != pairs_4[c].charAt(0))) v4++;
              if(valid(i+1,j) && (grid[i+1][j] != pairs_3[c].charAt(0))) v4++;
              if(valid(i,j+1) && (grid[i][j+1] != pairs_3[c].charAt(1))) v4++;
              if(valid(i+1,j+1) && (grid[i+1][j+1] != pairs_4[c].charAt(1))) v4++;
            }
            cur_ans += Math.min(Math.min(v1, v2), Math.min(v3, v4));
          }

          if(cur_ans < ans) {
            ans = cur_ans;
            type = 2;
            index = c;
          }

        }

        if(type == 1) {
          for(int i=0; i<n; i++) {
            if((i%2) == 1) {
            String r1= repeat(pairs[index], m);
            String r2 = repeat(pairs_2[index], m);
            int v1 = compare(grid_s[i], r1);
            int v2 = compare(grid_s[i], r2);
            if(v1 < v2) out.println(r1);
            else out.println(r2);
            }
            else {
              String r1= repeat(n_pairs[index], m);
              String r2 = repeat(n_pairs_2[index], m);
              int v1 = compare(grid_s[i], r1);
              int v2 = compare(grid_s[i], r2);
              if(v1 < v2) out.println(r1);
              else out.println(r2);
            }
          }
        }
        else {
          char[][] ans_grid = new char[n][m];
          int c = index;
          for(int j=0; j<m; j+=2) {
            int v1 = 0;
            for(int i=0; i<n; i+=2) {
              if(valid(i,j) && (grid[i][j] != pairs_3[c].charAt(0))) v1++;
              if(valid(i+1,j) && (grid[i+1][j] != pairs_4[c].charAt(0))) v1++;
              if(valid(i,j+1) && (grid[i][j+1] != pairs_3[c].charAt(1))) v1++;
              if(valid(i+1,j+1) && (grid[i+1][j+1] != pairs_4[c].charAt(1))) v1++;
            }
            int v2 = 0;
            for(int i=0; i<n; i+=2) {
              if(valid(i,j) && (grid[i][j] != pairs_4[c].charAt(0))) v2++;
              if(valid(i+1,j) && (grid[i+1][j] != pairs_3[c].charAt(0))) v2++;
              if(valid(i,j+1) && (grid[i][j+1] != pairs_4[c].charAt(1))) v2++;
              if(valid(i+1,j+1) && (grid[i+1][j+1] != pairs_3[c].charAt(1))) v2++;
            }
            int v3 = 0;
            for(int i=0; i<n; i+=2) {
              if(valid(i,j) && (grid[i][j] != pairs_3[c].charAt(0))) v3++;
              if(valid(i+1,j) && (grid[i+1][j] != pairs_4[c].charAt(0))) v3++;
              if(valid(i,j+1) && (grid[i][j+1] != pairs_4[c].charAt(1))) v3++;
              if(valid(i+1,j+1) && (grid[i+1][j+1] != pairs_3[c].charAt(1))) v3++;
            }
            int v4 = 0;
            for(int i=0; i<n; i+=2) {
              if(valid(i,j) && (grid[i][j] != pairs_4[c].charAt(0))) v4++;
              if(valid(i+1,j) && (grid[i+1][j] != pairs_3[c].charAt(0))) v4++;
              if(valid(i,j+1) && (grid[i][j+1] != pairs_3[c].charAt(1))) v4++;
              if(valid(i+1,j+1) && (grid[i+1][j+1] != pairs_4[c].charAt(1))) v4++;
            }
            if(v1 == Math.min(v1, Math.min(v2, Math.min(v3, v4)))) {
              for(int i=0; i<n; i+=2) {
              if(valid(i, j)) ans_grid[i][j] = pairs_3[c].charAt(0);
              if(valid(i+1, j)) ans_grid[i+1][j] = pairs_4[c].charAt(0);
              if(valid(i, j+1)) ans_grid[i][j+1] = pairs_3[c].charAt(1);
              if(valid(i+1, j+1)) ans_grid[i+1][j+1] = pairs_4[c].charAt(1);
              }
            }
            else if(v2 == Math.min(v1, Math.min(v2, Math.min(v3, v4)))) {
              for(int i=0; i<n; i+=2) {
              if(valid(i, j)) ans_grid[i][j] = pairs_4[c].charAt(0);
              if(valid(i+1, j)) ans_grid[i+1][j] = pairs_3[c].charAt(0);
              if(valid(i, j+1)) ans_grid[i][j+1] = pairs_4[c].charAt(1);
              if(valid(i+1, j+1)) ans_grid[i+1][j+1] = pairs_3[c].charAt(1);
              }
            }
            else if(v3 == Math.min(v1, Math.min(v2, Math.min(v3, v4)))) {
              for(int i=0; i<n; i+=2) {
              if(valid(i, j)) ans_grid[i][j] = pairs_3[c].charAt(0);
              if(valid(i+1, j)) ans_grid[i+1][j] = pairs_4[c].charAt(0);
              if(valid(i, j+1)) ans_grid[i][j+1] = pairs_4[c].charAt(1);
              if(valid(i+1, j+1)) ans_grid[i+1][j+1] = pairs_3[c].charAt(1);
              }
            }
            else {
              for(int i=0; i<n; i+=2) {
              if(valid(i, j)) ans_grid[i][j] = pairs_4[c].charAt(0);
              if(valid(i+1, j)) ans_grid[i+1][j] = pairs_3[c].charAt(0);
              if(valid(i, j+1)) ans_grid[i][j+1] = pairs_3[c].charAt(1);
              if(valid(i+1, j+1)) ans_grid[i+1][j+1] = pairs_4[c].charAt(1);
              }
            }
          }
          for(int i=0; i<n; i++) {
            StringBuilder sb = new StringBuilder();
            for(int j=0; j<m; j++) sb.append(ans_grid[i][j]);
            out.println(sb.toString());
          }
        }
        //  out.println(ans);

        out.close(); System.exit(0);
    }
    public static String repeat(String s, int length) {
      StringBuilder sb = new StringBuilder();
      for(int i=0; i<length; i++) sb.append(s.charAt((i % s.length())));
      return sb.toString();
    }
    public static int compare(String a, String b) {
      int count = 0;
      for(int i=0; i<a.length(); i++) if(a.charAt(i) != b.charAt(i)) count++;
      return count;
    }
    public static boolean valid(int i, int j) {
      return ((i<n) && (j<m));
    }
}
