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.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.InputMismatchException;
import java.io.IOException;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        ENiceTable solver = new ENiceTable();
        solver.solve(1, in, out);
        out.close();
    }

    static class ENiceTable {
        public void solve(int testNumber, InputReader in, PrintWriter out) {
            char[] c = {'A', 'G', 'C', 'T'};
            int n = 0, m = 0;
            n = in.ni();
            m = in.ni();
            char a[][] = new char[n][];
            for (int i = 0; i < n; i++) {
                a[i] = in.next().toCharArray();
            }
            int min = n * m;
            char ans[][] = new char[n][m];
            for (int i = 0; i < 3; i++) {
                for (int j = i + 1; j < 4; j++) {
                    char tm[][] = new char[n][m];
                    char tm1[][] = new char[n][m];
                    char e[] = {c[i], c[j]};
                    char o[] = new char[2];
                    for (int i1 = 0, j1 = 0; i1 < 4; i1++) {
                        if (e[0] != c[i1] && e[1] != c[i1]) {
                            o[j1++] = c[i1];
                        }
                    }
                    //System.out.println(e[0]+" "+e[1]+" "+o[0]+" "+o[1]);
                    int cost1 = 0, cost2 = 0;
                    for (int i1 = 0; i1 < n; i1++) {
                        int c1 = 0, c2 = 0;
                        char tc[][] = new char[2][m];
                        for (int j1 = 0; j1 < m; j1++) {
                            if ((i1 & 1) == 0) {
                                if ((j1 & 1) == 0) {
                                    tc[0][j1] = e[0];
                                    c1 += a[i1][j1] == e[0] ? 0 : 1;
                                } else {
                                    tc[0][j1] = e[1];
                                    c1 += a[i1][j1] == e[1] ? 0 : 1;
                                }
                            } else {
                                if ((j1 & 1) == 0) {
                                    tc[0][j1] = o[0];
                                    c1 += a[i1][j1] == o[0] ? 0 : 1;
                                } else {
                                    tc[0][j1] = o[1];
                                    c1 += a[i1][j1] == o[1] ? 0 : 1;
                                }
                            }
                        }
                        for (int j1 = 0; j1 < m; j1++) {
                            if ((i1 & 1) == 0) {
                                if ((j1 & 1) == 0) {
                                    tc[1][j1] = e[1];
                                    c2 += a[i1][j1] == e[1] ? 0 : 1;
                                } else {
                                    tc[1][j1] = e[0];
                                    c2 += a[i1][j1] == e[0] ? 0 : 1;
                                }
                            } else {
                                if ((j1 & 1) == 0) {
                                    tc[1][j1] = o[1];
                                    c2 += a[i1][j1] == o[1] ? 0 : 1;
                                } else {
                                    tc[1][j1] = o[0];
                                    c2 += a[i1][j1] == o[0] ? 0 : 1;
                                }
                            }
                        }
                        if (c1 < c2) {
                            tm[i1] = tc[0];
                            cost1 += c1;
                        } else {
                            tm[i1] = tc[1];
                            cost1 += c2;
                        }
                        //System.out.println(c1+" "+c2+" "+i1+" "+ Arrays.toString(tm[i1])+" "+cost);
                    }
                    for (int i1 = 0; i1 < m; i1++) {
                        int c1 = 0, c2 = 0;
                        char tc[][] = new char[2][n];
                        for (int j1 = 0; j1 < n; j1++) {
                            if ((i1 & 1) == 0) {
                                if ((j1 & 1) == 0) {
                                    tc[0][j1] = e[0];
                                    c1 += a[j1][i1] == e[0] ? 0 : 1;
                                } else {
                                    tc[0][j1] = e[1];
                                    c1 += a[j1][i1] == e[1] ? 0 : 1;
                                }
                            } else {
                                if ((j1 & 1) == 0) {
                                    tc[0][j1] = o[0];
                                    c1 += a[j1][i1] == o[0] ? 0 : 1;
                                } else {
                                    tc[0][j1] = o[1];
                                    c1 += a[j1][i1] == o[1] ? 0 : 1;
                                }
                            }
                        }
                        for (int j1 = 0; j1 < n; j1++) {
                            if ((i1 & 1) == 0) {
                                if ((j1 & 1) == 0) {
                                    tc[1][j1] = e[1];
                                    c2 += a[j1][i1] == e[1] ? 0 : 1;
                                } else {
                                    tc[1][j1] = e[0];
                                    c2 += a[j1][i1] == e[0] ? 0 : 1;
                                }
                            } else {
                                if ((j1 & 1) == 0) {
                                    tc[1][j1] = o[1];
                                    c2 += a[j1][i1] == o[1] ? 0 : 1;
                                } else {
                                    tc[1][j1] = o[0];
                                    c2 += a[j1][i1] == o[0] ? 0 : 1;
                                }
                            }
                        }
                        if (c1 < c2) {
                            for (int j1 = 0; j1 < n; j1++) {
                                tm1[j1][i1] = tc[0][j1];
                            }
                            cost2 += c1;
                        } else {
                            for (int j1 = 0; j1 < n; j1++) {
                                tm1[j1][i1] = tc[1][j1];
                            }
                            cost2 += c2;
                        }
                        //System.out.println(c1+" "+c2+" "+i1+" "+ Arrays.toString(tm[i1])+" "+cost);
                    }
                    if (cost1 < min) {
                        min = cost1;
                        ans = tm;
                    }
                    if (cost2 < min) {
                        min = cost2;
                        ans = tm1;
                    }
                }
            }
            for (char ct[] : ans) {
                for (char cc : ct) {
                    out.print(cc);
                }
                out.println();
            }
        }

    }

    static class InputReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;
        private InputReader.SpaceCharFilter filter;

        public InputReader(InputStream stream) {
            this.stream = stream;
        }

        public int read() {
            if (numChars == -1)
                throw new InputMismatchException();

            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }

                if (numChars <= 0)
                    return -1;
            }
            return buf[curChar++];
        }

        public int nextInt() {
            int c = read();

            while (isSpaceChar(c))
                c = read();

            int sgn = 1;

            if (c == '-') {
                sgn = -1;
                c = read();
            }

            int res = 0;
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            }
            while (!isSpaceChar(c));

            return res * sgn;
        }

        public String readString() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = read();
            }
            while (!isSpaceChar(c));

            return res.toString();
        }

        public boolean isSpaceChar(int c) {
            if (filter != null)
                return filter.isSpaceChar(c);
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        public String next() {
            return readString();
        }

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

        public interface SpaceCharFilter {
            public boolean isSpaceChar(int ch);

        }

    }
}

