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.*;

public class B530 {
    public static void main(String[] args) {
        MyScanner sc = new MyScanner();
        PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
        int n = sc.nextInt(); int m = sc.nextInt();
        int [][] a = new int[n][m];
        for (int i = 0; i < n; i++) {
            String s = sc.next();
            for (int j = 0; j < m; j++) {
                if (s.charAt(j) == 'A') a[i][j] = 0;
                else if (s.charAt(j) == 'G') a[i][j] = 1;
                else if (s.charAt(j) == 'T') a[i][j] = 2;
                else a[i][j] = 3;
            }
        }
        int ans = Integer.MAX_VALUE;
        int [][] best = new int[n][m];
        for (int i = 0; i < 4; i++) {
            for (int j = i + 1; j < 4; j++) {
                int [] one = new int[n];
                int [] two = new int[n];
                int [] three = new int[n];
                int [] four = new int [n];
                int b = -1; int c = -1;
                for (int t = 0; t < 4; t++) {
                    if (t != i && t != j && b == -1) b = t;
                    else if (t != i && t != j) c = t;
                }
                for (int row = 0; row < n; row++) {
                    if (row % 2 == 0) {
                        for (int col = 0; col < m; col++) {
                            if (col % 2 == 0) {
                                if (a[row][col] != i) one[row]++;
                                if (a[row][col] != j) two[row]++;
                            } else {
                                if (a[row][col] != j) one[row]++;
                                if (a[row][col] != i) two[row]++;
                            }
                        }
                    } else {
                        for (int col = 0; col < m; col++) {
                            if (col % 2 == 0) {
                                if (a[row][col] != b) three[row]++;
                                if (a[row][col] != c) four[row]++;
                            } else {
                                if (a[row][col] != c) three[row]++;
                                if (a[row][col] != b) four[row]++;
                            }
                        }
                    }
                }
                int ret = 0;
                for (int row = 0; row < n; row++) {
                    if (row % 2 == 0) ret += Math.min(one[row], two[row]);
                    else ret += Math.min(three[row], four[row]);
                }
                if (ret < ans) {
                    ans = ret;
                    for (int row = 0; row < n; row++) {
                        for (int col = 0; col < m; col++) {
                            if (row % 2 == 0) {
                                if (one[row] < two[row]) {
                                    if (col % 2 == 0) best[row][col] = i; else best[row][col] = j;
                                } else {
                                    if (col % 2 == 0) best[row][col] = j; else best[row][col] = i;
                                }
                            } else {
                                if (three[row] < four[row]) {
                                    if (col % 2 == 0) best[row][col] = b; else best[row][col] = c;
                                } else {
                                    if (col % 2 == 0) best[row][col] = c; else best[row][col] = b;
                                }
                            }
                        }
                    }
                }
            }
        }
        for (int i = 0; i < 4; i++) {
            for (int j = i + 1; j < 4; j++) {
                int [] one = new int[m];
                int [] two = new int[m];
                int [] three = new int[m];
                int [] four = new int [m];
                int b = -1; int c = -1;
                for (int t = 0; t < 4; t++) {
                    if (t != i && t != j && b == -1) b = t;
                    else if (t != i && t != j) c = t;
                }
                for (int col = 0; col < m; col++) {
                    if (col % 2 == 0) {
                        for (int row = 0; row < n; row++) {
                            if (row % 2 == 0) {
                                if (a[row][col] != i) one[col]++;
                                if (a[row][col] != j) two[col]++;
                            } else {
                                if (a[row][col] != j) one[col]++;
                                if (a[row][col] != i) two[col]++;
                            }
                        }
                    } else {
                        for (int row = 0; row < n; row++) {
                            if (row % 2 == 0) {
                                if (a[row][col] != b) three[col]++;
                                if (a[row][col] != c) four[col]++;
                            } else {
                                if (a[row][col] != c) three[col]++;
                                if (a[row][col] != b) four[col]++;
                            }
                        }
                    }
                }
                int ret = 0;
                for (int col = 0; col < m; col++) {
                    if (col % 2 == 0) ret += Math.min(one[col], two[col]);
                    else ret += Math.min(three[col], four[col]);
                }
                if (ret < ans) {
                    ans = ret;
                    for (int row = 0; row < n; row++) {
                        for (int col = 0; col < m; col++) {
                            if (col % 2 == 0) {
                                if (one[col] < two[col]) {
                                    if (row % 2 == 0) best[row][col] = i; else best[row][col] = j;
                                } else {
                                    if (row % 2 == 0) best[row][col] = j; else best[row][col] = i;
                                }
                            } else {
                                if (three[col] < four[col]) {
                                    if (row % 2 == 0) best[row][col] = b; else best[row][col] = c;
                                } else {
                                    if (row % 2 == 0) best[row][col] = c; else best[row][col] = b;
                                }
                            }
                        }
                    }
                }
            }
        }
        String [] map = new String[]{"A", "G", "T", "C"};
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                out.print(map[best[i][j]]);
            }
            out.println();
        }
        out.close();
    }


    //-----------MyScanner class for faster input----------
    public static class MyScanner {
        BufferedReader br;
        StringTokenizer st;

        public MyScanner() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }


    }

}