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.
/**
 * @author derrick20
 */
import java.io.*;
import java.util.*;

public class NiceTable {
    public static void main(String args[]) throws Exception {
        FastScanner sc = new FastScanner();
        PrintWriter out = new PrintWriter(System.out);

        int N = sc.nextInt();
        int M = sc.nextInt();
        char[][] table = new char[N][M];
        for (int i = 0; i < N; i++) {
            table[i] = sc.next().toCharArray();
        }
        HashSet<Character> unused = new HashSet<>();
        unused.add('A');
        unused.add('T');
        unused.add('C');
        unused.add('G');
        permutations = new ArrayList<>();
        permute("", 0, unused);

        for (String permutation : permutations) {
            solve(table, permutation, false);
        }
        table = transpose(table);
        for (String permutation : permutations) {
            solve(table, permutation, true);
        }

        for (int r = 0; r < N; r++) {
            for (int c = 0; c < M; c++) {
                out.print(ans[r][c]);
            }
            out.println();
        }
        out.close();
    }

    static char[][] transpose(char[][] table) {
        char[][] res = new char[table[0].length][table.length];
        for (int r = 0; r < table.length; r++) {
            for (int c = 0; c < table[0].length; c++) {
                res[c][r] = table[r][c];
            }
        }
        return res;
    }

    static char[][] ans;
    static int minCost = (int) 1e9;
    // each row can reach another row by using the other
    // AB CD
    // BA CD
    // AB DC
    // BA DC
    // Try each combination for each row, alternating
    // ABABABAB... first row, CDCDCDCD... second row
    // each row is independent (only they must alternate), so we just need
    // to optimize row by row.
    static void solve(char[][] table, String permutation, boolean transposed) {
        // let AB = first two, CD = last two
        char[][] pattern = new char[2][2];
        pattern[0] = new char[]{permutation.charAt(0), permutation.charAt(1)};
        pattern[1] = new char[]{permutation.charAt(2), permutation.charAt(3)};
        char[][] res = new char[table.length][table[0].length];
        int cost = 0;
        for (int r = 0; r < table.length; r++) {
            // We maintain two counts: doing ababab... and bababa
            // since it's allowed to alternate
            int costF = 0;
            int costR = 0;
            char[] addF = new char[table[0].length];
            char[] addR = new char[table[0].length];

            for (int c = 0; c < table[0].length; c++) {
                costF += pattern[r % 2][c % 2] == table[r][c] ? 0 : 1;
                addF[c] = pattern[r % 2][c % 2];

                costR += pattern[r % 2][1 - (c % 2)] == table[r][c] ? 0 : 1;
                addR[c] = pattern[r % 2][1 - (c % 2)];
            }
            if (costF < costR) {
                res[r] = addF;
                cost += costF;
            }
            else {
                res[r] = addR;
                cost += costR;
            }
        }
        if (cost < minCost) {
            minCost = cost;
            if (transposed) {
                ans = transpose(res);
            }
            else {
                ans = res;
            }
        }
    }

    static ArrayList<String> permutations;

    static void permute(String res, int i, HashSet<Character> unused) {
        if (unused.size() == 0) {
            permutations.add(res);
        }
        else {
            for (char c : unused) {
                HashSet<Character> copy = new HashSet<>(unused);
                copy.remove(c);
                permute(res + c, i + 1, copy);
            }
        }
    }

    static class FastScanner {
        public int BS = 1<<16;
        public char NC = (char)0;
        byte[] buf = new byte[BS];
        int bId = 0, size = 0;
        char c = NC;
        double cnt = 1;
        BufferedInputStream in;

        public FastScanner() {
            in = new BufferedInputStream(System.in, BS);
        }

        public FastScanner(String s) {
            try {
                in = new BufferedInputStream(new FileInputStream(new File(s)), BS);
            }
            catch (Exception e) {
                in = new BufferedInputStream(System.in, BS);
            }
        }

        private char getChar(){
            while(bId==size) {
                try {
                    size = in.read(buf);
                }catch(Exception e) {
                    return NC;
                }
                if(size==-1)return NC;
                bId=0;
            }
            return (char)buf[bId++];
        }

        public int nextInt() {
            return (int)nextLong();
        }

        public int[] nextInts(int N) {
            int[] res = new int[N];
            for (int i = 0; i < N; i++) {
                res[i] = (int) nextLong();
            }
            return res;
        }

        public long[] nextLongs(int N) {
            long[] res = new long[N];
            for (int i = 0; i < N; i++) {
                res[i] = nextLong();
            }
            return res;
        }

        public long nextLong() {
            cnt=1;
            boolean neg = false;
            if(c==NC)c=getChar();
            for(;(c<'0' || c>'9'); c = getChar()) {
                if(c=='-')neg=true;
            }
            long res = 0;
            for(; c>='0' && c <='9'; c=getChar()) {
                res = (res<<3)+(res<<1)+c-'0';
                cnt*=10;
            }
            return neg?-res:res;
        }

        public double nextDouble() {
            double cur = nextLong();
            return c!='.' ? cur:cur+nextLong()/cnt;
        }

        public String next() {
            StringBuilder res = new StringBuilder();
            while(c<=32)c=getChar();
            while(c>32) {
                res.append(c);
                c=getChar();
            }
            return res.toString();
        }

        public String nextLine() {
            StringBuilder res = new StringBuilder();
            while(c<=32)c=getChar();
            while(c!='\n') {
                res.append(c);
                c=getChar();
            }
            return res.toString();
        }

        public boolean hasNext() {
            if(c>32)return true;
            while(true) {
                c=getChar();
                if(c==NC)return false;
                else if(c>32)return true;
            }
        }
    }
}