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.
//package codeforces.contests.round530;

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.InputMismatchException;
import java.util.List;

/**
 * @author tainic on Jan 5, 2019
 */
public class E {

    private static boolean LOCAL;
    static {
        try { LOCAL = "aurel".equalsIgnoreCase(System.getenv().get("USER")); } catch (Exception e){}
    }

    private static final String TEST =
        "3 5\n" +
        "AGCAG\n" +
        "AGCAG\n" +
        "AGCAG";

    void solve(InputReader in, PrintWriter out) {
        int r = in.nextInt();
        int c = in.nextInt();
        char[][] a = new char[r][c];
        for (int i = 0; i < r; i++) {
            a[i] = in.next().toCharArray();
        }

        List<char[][]> pos = Arrays.asList(
            new char[][]{{'A', 'C'}, {'G', 'T'}},
            new char[][]{{'A', 'G'}, {'C', 'T'}},
            new char[][]{{'A', 'T'}, {'C', 'G'}},
            new char[][]{{'C', 'G'}, {'A', 'T'}},
            new char[][]{{'C', 'T'}, {'A', 'G'}},
            new char[][]{{'G', 'T'}, {'A', 'C'}}
        );
        Sol best = null;
        for (char[][] p : pos) {
            Sol sol = fRows(a, p);
            if (best == null || sol.changes < best.changes) {
                best = sol;
            }
            sol = fCols(a, p);
            if (best == null || sol.changes < best.changes) {
                best = sol;
            }
        }

        System.err.println(best.changes);
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                out.print(best.sol[i][j]);
            }
            out.println();
        }
    }

    private Sol fRows(char[][] a, char[][] p) {
        Sol sol = new Sol();
        sol.sol = new char[a.length][a[0].length];
        for (int r = 0; r < a.length; r++) {
            int rowChanges = a[0].length + 1;
            for (int d = 0; d <= 1; d++) {
                int dChanges = 0;
                char[] newRow = new char[a[0].length];
                for (int c = 0; c < newRow.length; c++) {
                    if (a[r][c] != p[r % 2][(c + d) % 2]) {
                        dChanges++;
                    }
                    newRow[c] = p[r % 2][(c + d) % 2];
                }
                if (dChanges < rowChanges) {
                    sol.sol[r] = newRow;
                    rowChanges = dChanges;
                }
            }
            sol.changes += rowChanges;
        }
        return sol;
    }

    private Sol fCols(char[][] a, char[][] p) {
        Sol sol = new Sol();
        sol.sol = new char[a.length][a[0].length];
        for (int c = 0; c < a[0].length; c++) {
            int colChanges = a.length + 1;
            for (int d = 0; d <= 1; d++) {
                int dChanges = 0;
                char[] newCol = new char[a.length];
                for (int r = 0; r < newCol.length; r++) {
                    if (a[r][c] != p[c % 2][(r + d) % 2]) {
                        dChanges++;
                    }
                    newCol[r] = p[c % 2][(r + d) % 2];
                }
                if (dChanges < colChanges) {
                    for (int r = 0; r < newCol.length; r++) {
                        sol.sol[r][c] = newCol[r];
                    }
                    colChanges = dChanges;
                }
            }
            sol.changes += colChanges;
        }
        return sol;
    }

    class Sol {
        int changes = 0;
        char[][] sol;
    }

    //region main
    public static void main(String[] args) throws Exception {
        long t = System.currentTimeMillis();

        try (
            InputReader in = new StreamInputReader(!LOCAL ? System.in : new ByteArrayInputStream(TEST.getBytes()));
            PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out, 2048), false)
        ) {
            new E().solve(in, out);
        }

        System.err.println("time: " + (System.currentTimeMillis() - t) + "ms");
    }
    //endregion

    //region fast io
    abstract static class InputReader implements AutoCloseable {

        public abstract int read();

        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 long nextLong() {
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            long 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 next() {
            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) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }
    }

    static class StreamInputReader extends InputReader {

        private InputStream stream;
        private byte[] buf;
        private int curChar, numChars;

        public StreamInputReader(InputStream stream) {
            this(stream, 2048);
        }

        public StreamInputReader(InputStream stream, int bufSize) {
            this.stream = stream;
            this.buf = new byte[bufSize];
        }

        @Override
        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++];
        }

        @Override
        public void close() throws Exception {
            stream.close();
        }

    }
    //endregion

    //region imports
    //endregion

}