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.io.*;
import java.math.BigInteger;
import java.util.*;

public class A {
    static MyScanner sc;
    static PrintWriter pw;

    public static void main(String[] args) throws Throwable {
        sc = new MyScanner();
        pw = new PrintWriter(System.out);

        char[] map = {'A', 'G', 'C', 'T'};
        HashMap<Character, Integer> map2 = new HashMap<>();
        map2.put('A', 0);
        map2.put('G', 1);
        map2.put('C', 2);
        map2.put('T', 3);


        int n = sc.nextInt();
        int m = sc.nextInt();
        int[][] a = new int[n][m];
        for (int i = 0; i < n; i++) {
            char[] in = sc.next().toCharArray();
            for (int j = 0; j < m; j++)
                a[i][j] = map2.get(in[j]);
        }
        int maxCommon = 0;
        int[][] ans = new int[n][m];


        // ROWS
        for (int c1 = 0; c1 < 4; c1++)
            for (int c2 = 0; c2 < 4; c2++) {
                if (c1 == c2)
                    continue;
                int c3 = 0;
                while (c3 == c1 || c3 == c2)
                    c3++;
                int c4 = 0;
                while (c4 == c1 || c4 == c2 || c4 == c3)
                    c4++;

                int[][] tmp = new int[n][m];
                int cntCommon = 0;

                for (int i = 0; i < n; i++) {
                    int common12 = 0, common21 = 0;
                    if (i % 2 == 0) {
                        for (int j = 0; j < m; j++) {
                            if (j % 2 == 0) {
                                if (a[i][j] == c1)
                                    common12++;
                                else if (a[i][j] == c2)
                                    common21++;
                            } else {
                                if (a[i][j] == c2)
                                    common12++;
                                else if (a[i][j] == c1)
                                    common21++;
                            }
                        }
                        if (common12 > common21) {
                            for (int j = 0; j < m; j++)
                                tmp[i][j] = (j % 2 == 0) ? c1 : c2;
                        } else {
                            for (int j = 0; j < m; j++)
                                tmp[i][j] = (j % 2 == 0) ? c2 : c1;
                        }
                    } else {
                        for (int j = 0; j < m; j++) {
                            if (j % 2 == 0) {
                                if (a[i][j] == c3)
                                    common12++;
                                else if (a[i][j] == c4)
                                    common21++;
                            } else {
                                if (a[i][j] == c4)
                                    common12++;
                                else if (a[i][j] == c3)
                                    common21++;
                            }
                        }
                        if (common12 > common21) {
                            for (int j = 0; j < m; j++)
                                tmp[i][j] = (j % 2 == 0) ? c3 : c4;
                        } else {
                            for (int j = 0; j < m; j++)
                                tmp[i][j] = (j % 2 == 0) ? c4 : c3;
                        }
                    }
                    cntCommon += Math.max(common12, common21);
                }
                if (cntCommon >= maxCommon) {
                    ans = tmp;
                    maxCommon = cntCommon;
                }
            }

        // COLUMNS
        for (int c1 = 0; c1 < 4; c1++)
            for (int c2 = 0; c2 < 4; c2++) {
                if (c1 == c2)
                    continue;
                int c3 = 0;
                while (c3 == c1 || c3 == c2)
                    c3++;
                int c4 = 0;
                while (c4 == c1 || c4 == c2 || c4 == c3)
                    c4++;

                int[][] tmp = new int[n][m];
                int cntCommon = 0;

                for (int j = 0; j < m; j++) {
                    int common12 = 0, common21 = 0;
                    if (j % 2 == 0) {
                        for (int i = 0; i < n; i++) {
                            if (i % 2 == 0) {
                                if (a[i][j] == c1)
                                    common12++;
                                else if (a[i][j] == c2)
                                    common21++;
                            } else {
                                if (a[i][j] == c2)
                                    common12++;
                                else if (a[i][j] == c1)
                                    common21++;
                            }
                        }
                        if (common12 > common21) {
                            for (int i = 0; i < n; i++)
                                tmp[i][j] = (i % 2 == 0) ? c1 : c2;
                        } else {
                            for (int i = 0; i < n; i++)
                                tmp[i][j] = (i % 2 == 0) ? c2 : c1;
                        }
                    } else {
                        for (int i = 0; i < n; i++) {
                            if (i % 2 == 0) {
                                if (a[i][j] == c3)
                                    common12++;
                                else if (a[i][j] == c4)
                                    common21++;
                            } else {
                                if (a[i][j] == c4)
                                    common12++;
                                else if (a[i][j] == c3)
                                    common21++;
                            }
                        }
                        if (common12 > common21) {
                            for (int i = 0; i < n; i++)
                                tmp[i][j] = (i % 2 == 0) ? c3 : c4;
                        } else {
                            for (int i = 0; i < n; i++)
                                tmp[i][j] = (i % 2 == 0) ? c4 : c3;
                        }
                    }
                    cntCommon += Math.max(common12, common21);
                }
                if (cntCommon >= maxCommon) {
                    ans = tmp;
                    maxCommon = cntCommon;
                }
            }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++)
                pw.print(map[ans[i][j]]);
            pw.println();
        }


        pw.flush();
        pw.close();
    }

    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;
        }
    }
}