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 cf1099;

import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.InputMismatchException;
import java.util.List;

public class CFE {
    private static final String INPUT = "3 5\n" +
            "AGCAG\n" +
            "AGCAG\n" +
            "AGCAG\n";

    private PrintWriter out;
    private FastScanner sc;

    public static void main(String[] args) {
        new CFE().run();
    }

    public void run() {
        sc = new FastScanner(oj ? System.in : new ByteArrayInputStream(INPUT.getBytes()));
        out = new PrintWriter(System.out);

        long s = System.currentTimeMillis();
        solve();
        out.flush();
        tr(System.currentTimeMillis() - s + "ms");
    }

    public void solve() {
        int n = sc.nextInt();
        int m = sc.nextInt();
        char[][] lines = new char[n][m];
        for (int i = 0; i < n; i++) lines[i] = sc.nextLine().toCharArray();
        char A = 'A', G = 'G', C = 'C', T = 'T';

        int hch = Integer.MAX_VALUE;
        int vch = Integer.MAX_VALUE;
        char[][] hans = new char[n][2];
        char[][] vans = new char[m][2];
        char[][][] pairs = {{{A, G}, {C, T}}, {{A, C}, {G, T}}, {{A, T}, {G, C}}, {{G, C}, {A, T}}, {{G, T}, {A, C}}, {{C, T}, {A, G}}};

        char[][] chans = new char[n][2];
        for (char[][] pair : pairs) {
            int ch = 0;
            for (int i = 0; i < n; i++) {
                int ch1 = 0;
                int ch2 = 0;
                for (int j = 0; j < m; j += 2) {
                    if (j + 0 < m && pair[i % 2][0] != lines[i][j + 0]) ch1++;
                    if (j + 1 < m && pair[i % 2][1] != lines[i][j + 1]) ch1++;
                    if (j + 0 < m && pair[i % 2][1] != lines[i][j + 0]) ch2++;
                    if (j + 1 < m && pair[i % 2][0] != lines[i][j + 1]) ch2++;
                }
                if (ch1 < ch2) {
                    chans[i][0] = pair[i % 2][0];
                    chans[i][1] = pair[i % 2][1];
                    ch += ch1;
                } else {
                    chans[i][0] = pair[i % 2][1];
                    chans[i][1] = pair[i % 2][0];
                    ch += ch2;
                }
            }
            if (ch < hch) {
                for (int i = 0; i < n; i++) {
                    hans[i][0] = chans[i][0];
                    hans[i][1] = chans[i][1];
                }
                hch = ch;
            }
        }

        char[][] cvans = new char[m][2];
        for (char[][] pair : pairs) {
            int ch = 0;
            for (int i = 0; i < m; i++) {
                int ch1 = 0;
                int ch2 = 0;
                for (int j = 0; j < n; j += 2) {
                    if (j + 0 < n && pair[i % 2][0] != lines[j + 0][i]) ch1++;
                    if (j + 1 < n && pair[i % 2][1] != lines[j + 1][i]) ch1++;
                    if (j + 0 < n && pair[i % 2][1] != lines[j + 0][i]) ch2++;
                    if (j + 1 < n && pair[i % 2][0] != lines[j + 1][i]) ch2++;
                }
                if (ch1 < ch2) {
                    cvans[i][0] = pair[i % 2][0];
                    cvans[i][1] = pair[i % 2][1];
                    ch += ch1;
                } else {
                    cvans[i][0] = pair[i % 2][1];
                    cvans[i][1] = pair[i % 2][0];
                    ch += ch2;
                }
            }
            if (ch < vch) {
                for (int i = 0; i < m; i++) {
                    vans[i][0] = cvans[i][0];
                    vans[i][1] = cvans[i][1];
                }
                vch = ch;
            }
        }

//        System.out.println(vch + " " + hch);
        char[][] ans = new char[n][m];
        if (vch < hch) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    ans[i][j] = vans[j][i%2];
                }
            }
        } else {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    ans[i][j] = hans[i][j%2];
                }
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                out.print(ans[i][j]);
            }
            out.println();
        }
    }
    //********************************************************************************************
    //********************************************************************************************
    //********************************************************************************************

    /**
     * If searched element doesn't exist, returns index of first element which is bigger than searched value.<br>
     * If searched element is bigger than any array element function returns first index after last element.<br>
     * If searched element is lower than any array element function returns index of first element.<br>
     * If there are many values equals searched value function returns first occurrence.<br>
     */
    private static int lowerBound(long[] arr, long key) {
        int lo = 0;
        int hi = arr.length - 1;
        while (lo < hi) {
            int mid = (lo + hi) / 2;
            if (key <= arr[mid]) {
                hi = mid - 1;
            } else {
                lo = mid + 1;
            }
        }
        return arr[lo] < key ? lo + 1 : lo;
    }

    /**
     * Returns index of first element which is grater than searched value.
     * If searched element is bigger than any array element, returns first index after last element.
     */
    private static int upperBound(long[] arr, long key) {
        int lo = 0;
        int hi = arr.length - 1;
        while (lo < hi) {
            int mid = (lo + hi) / 2;
            if (key >= arr[mid]) {
                lo = mid + 1;
            } else {
                hi = mid;
            }
        }
        return arr[lo] <= key ? lo + 1 : lo;
    }

    private static int ceil(double d) {
        int ret = (int) d;
        return ret == d ? ret : ret + 1;
    }

    private static int round(double d) {
        return (int) (d + 0.5);
    }

    private static int gcd(int a, int b) {
        BigInteger b1 = BigInteger.valueOf(a);
        BigInteger b2 = BigInteger.valueOf(b);
        BigInteger gcd = b1.gcd(b2);
        return gcd.intValue();
    }

    private static long gcd(long a, long b) {
        BigInteger b1 = BigInteger.valueOf(a);
        BigInteger b2 = BigInteger.valueOf(b);
        BigInteger gcd = b1.gcd(b2);
        return gcd.longValue();
    }

    private int[] readIntArray(int n) {
        int[] res = new int[n];
        for (int i = 0; i < n; i++) {
            res[i] = sc.nextInt();
        }
        return res;
    }

    private long[] readLongArray(int n) {
        long[] res = new long[n];
        for (int i = 0; i < n; i++) {
            res[i] = sc.nextLong();
        }
        return res;
    }

    @SuppressWarnings("unused")
    static class FastScanner {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;

        FastScanner(InputStream stream) {
            this.stream = stream;
        }

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

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

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

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

        public double nextDouble() {
            return Double.parseDouble(next());
        }

        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 String nextLine() {
            int c = read();
            while (isEndline(c))
                c = read();
            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = read();
            } while (!isEndline(c));
            return res.toString();
        }

    }

    private boolean oj = System.getProperty("ONLINE_JUDGE") != null;

    private void tr(Object... o) {
        if (!oj) System.out.println(Arrays.deepToString(o));
    }
}