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.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;

public class ENiceTable {

    public static void main(String[] args) throws Exception {
        PrintWriter writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
        Solution solution = new Solution(new InputReader(), writer);
        solution.solve();
        writer.close();
    }

    public static class Solution {
        private InputReader in;
        private PrintWriter writer;
        private char[][] table;
        private int n;
        private int m;

        Solution(InputReader input, PrintWriter writer) {
            this.in = input;
            this.writer = writer;
        }

        void solve() throws Exception {
            n = in.readInt();
            m = in.readInt();

            table = new char[n][m];
            for(int i = 0; i < n; i++){
                String line = in.readString();
                for(int j = 0; j < m; j++){
                    table[i][j] = line.charAt(j);
                }
            }

            char[] AC = new char[]{'A','C'};
            char[] AG = new char[]{'A','G'};
            char[] AT = new char[]{'A','T'};
            char[] CG = new char[]{'C','G'};
            char[] CT = new char[]{'C','T'};
            char[] GT = new char[]{'G','T'};

            List<NiceTable> niceTables = new ArrayList<>();
            niceTables.addAll(combinations(AC, GT));
            niceTables.addAll(combinations(AG, CT));
            niceTables.addAll(combinations(AT, CG));

            Collections.sort(niceTables);

            StringBuilder sb = new StringBuilder();
            char[][] solution = createTable(niceTables.get(0));
            for(int i = 0; i < solution.length; i++){
                for(int j = 0; j < solution[i].length; j++){
                    sb.append(solution[i][j]);
                }
                sb.append('\n');
            }
            writer.print(sb.toString());
        }

        char[][] createTable(NiceTable niceTable){
            boolean vertical = niceTable.vertical;
            char[][] solution = new char[n][m];
            int limit = vertical ? n:m;

            for(int i = 0; i < limit; i++){
                if(i%2==0){
                    popSolution(niceTable.first, niceTable.offsets.get(i), solution, vertical?i:0, vertical?0:i, vertical);
                } else{
                    popSolution(niceTable.second, niceTable.offsets.get(i), solution, vertical?i:0, vertical?0:i, vertical);
                }
            }

            return solution;
        }

        void popSolution(char[] set, int offset, char[][] solution, int x, int y, boolean vertical){
            int limit2 = vertical ? m:n;
            int dx = vertical?0:1;
            int dy = vertical?1:0;
            for(int i = 0; i<limit2; i++){
                solution[x][y] = set[(i+offset)%2];
                x+=dx;
                y+=dy;
            }
        }

        List<NiceTable> combinations(char[] first, char[] second){
            List<NiceTable> niceTables = new ArrayList<>();
            niceTables.add(diff(first, second, false));
            niceTables.add(diff(first, second, true));
            niceTables.add(diff(second, first, false));
            niceTables.add(diff(second, first, true));

            return  niceTables;
        }

        NiceTable diff(char[] first, char[] second, boolean vertical){
            int limit = vertical ? n:m;
            int sumDiff = 0;
            int diff1;
            int diff2;
            List<Integer> offsets = new ArrayList<>();
            for (int i = 0; i < limit; i++) {
                if (i % 2 == 0) {
                    diff1 = diff(first, 0, vertical?i:0, vertical?0:i, vertical);
                    diff2 = diff(first, 1, vertical?i:0, vertical?0:i, vertical);
                } else {
                    diff1 = diff(second, 0, vertical?i:0, vertical?0:i, vertical);
                    diff2 = diff(second, 1, vertical?i:0, vertical?0:i, vertical);
                }
                if(diff1 > diff2){
                    offsets.add(1);
                } else{
                    offsets.add(0);
                }
                sumDiff+= Math.min(diff1, diff2);
            }

            return new NiceTable(sumDiff, first, second, vertical, offsets);
        }

        int diff(char[] set, int offset, int x, int y, boolean vertical){
            int limit2 = vertical ? m:n;
            int dx = vertical?0:1;
            int dy = vertical?1:0;
            int diff = 0;
            for(int i = 0; i<limit2; i++){
                if(table[x][y]!=set[(i+offset)%2]){
                    diff++;
                }
                x+=dx;
                y+=dy;
            }

            return diff;
        }
    }

    public static class NiceTable implements Comparable<NiceTable>{
        int diff;
        char[] first;
        char[] second;
        boolean vertical;
        List<Integer> offsets = new ArrayList<>();

        NiceTable(int diff, char[] first, char[] second, boolean vertical, List<Integer> offsets){
            this.diff = diff;
            this.first = first;
            this.second = second;
            this.vertical = vertical;
            this.offsets = offsets;
        }

        @Override
        public int compareTo(NiceTable o) {
            return Integer.compare(this.diff, o.diff);
        }
    }

    public static class InputReader {
        BufferedReader stdin = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer("");

        String readString() throws Exception {
            while (!st.hasMoreTokens()) {
                st = new StringTokenizer(stdin.readLine());
            }
            return st.nextToken();
        }

        long readLong() throws Exception {
            return Long.parseLong(readString());
        }

        int readInt() throws Exception {
            return Integer.parseInt(readString());
        }
    }
}
