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

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author beginner1010
 */
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);
        TaskE solver = new TaskE();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskE {
        final String validCharacters = "AGCT";
        ArrayList<String> possibleStrings;
        StringBuffer curStr;
        int minCost;
        char[][] best;

        private void permutation(boolean[] visited) {
            if (curStr.length() == 4) {
                possibleStrings.add(curStr.toString());
                return;
            }
            for (int i = 0; i < 4; i++)
                if (visited[i] == false) {
                    visited[i] = true;
                    curStr = curStr.append(validCharacters.charAt(i));
                    permutation(visited);
                    curStr = curStr.deleteCharAt(curStr.length() - 1);
                    visited[i] = false;
                }
        }

        char[][] rotate(char[][] original) {
            int m = original.length;
            int n = original[0].length;
            char[][] ret = new char[n][m];
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    ret[j][i] = original[i][j];
                }
            }
            return ret;
        }

        void getMin(char[][] original, boolean needRotate) {
            if (needRotate == true) {
                original = rotate(original);
            }
            int m = original.length;
            int n = original[0].length;
            char[][] curMap = new char[m][n];
            for (String perm : possibleStrings) {
                int curCost = 0;
                for (int i = 0; i < m; i++) {
                    char first = i % 2 == 0 ? perm.charAt(0) : perm.charAt(2);
                    char second = i % 2 == 0 ? perm.charAt(1) : perm.charAt(3);
                    int[] rowCost = new int[2];
                    for (int z = 0; z < 2; z++) {
                        for (int j = 0; j < n; j++) {
                            char curCharacter = j % 2 == 0 ? first : second;
                            if (original[i][j] != curCharacter)
                                rowCost[z]++;
                        }
                        char temp = first;
                        first = second;
                        second = temp;
                    }
                    first = i % 2 == 0 ? perm.charAt(0) : perm.charAt(2);
                    second = i % 2 == 0 ? perm.charAt(1) : perm.charAt(3);
                    if (rowCost[1] < rowCost[0]) {
                        char temp = first;
                        first = second;
                        second = temp;
                    }
                    for (int j = 0; j < n; j++) {
                        char curCharacter = j % 2 == 0 ? first : second;
                        curMap[i][j] = curCharacter;
                    }
                    curCost += Math.min(rowCost[0], rowCost[1]);
                }
                if (curCost < minCost) {
                    minCost = curCost;
                    char[][] aux = needRotate == false ? curMap : rotate(curMap);
                    for (int i = 0; i < aux.length; i++) {
                        for (int j = 0; j < aux[0].length; j++) {
                            best[i][j] = (char) aux[i][j];
                        }
                    }
                }
            }
            return;
        }

        public void solve(int testNumber, InputReader in, PrintWriter out) {
            boolean[] visited = new boolean[4];
            this.curStr = new StringBuffer();
            this.possibleStrings = new ArrayList<>();
            permutation(visited);

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

            minCost = Integer.MAX_VALUE;
            best = new char[m][n];
            getMin(map, false);
            getMin(map, true);
            System.err.println(minCost);
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    out.print(best[i][j]);
                }
                out.println();
            }
        }

    }

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

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

        private boolean isWhitespace(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        private boolean isEndOfLine(int c) {
            return c == '\n' || c == '\r' || c == -1;
        }

        private 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 (isWhitespace(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 (!isWhitespace(c));
            return res * sgn;
        }

        public String nextLine() {
            int c = read();
            while (isWhitespace(c))
                c = read();
            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = read();
            } while (!isEndOfLine(c));
            return res.toString();
        }

    }
}

