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.OutputStream;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.UncheckedIOException;
import java.nio.charset.Charset;
import java.util.StringTokenizer;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.io.BufferedReader;
import java.io.InputStream;

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

    static class BNiceTable {
        private static final char[] DNA = {'A', 'C', 'G', 'T'};

        public void solve(int testNumber, LightScanner in, LightWriter out) {
            int n = in.ints(), m = in.ints();
            int[][] color = new int[n][m];
            for (int i = 0; i < n; i++) {
                String s = in.string();
                for (int j = 0; j < m; j++) {
                    color[i][j] = charToInt(s.charAt(j));
                }
            }

            int[][][] row = new int[2][4][n];
            int[][][] col = new int[2][4][m];
            for (int y = 0; y < n; y++) {
                for (int x = 0; x < m; x++) {
                    row[x % 2][color[y][x]][y]++;
                    col[y % 2][color[y][x]][x]++;
                }
            }

            boolean[] flagsR = new boolean[n];
            boolean[] flagsC = new boolean[m];

            int[][] p = new int[2][2];

            long ans = Long.MAX_VALUE;
            int[][] pattern = new int[2][2];
            boolean[] choice = null;
            boolean type = false;
            for (int z = 1; z < 4; z++) {
                for (int w = 0; w < z; w++) {
                    // build pattern
                    p[0][0] = w;
                    p[0][1] = z;
                    int unused = (~((1 << w) | (1 << z))) & 0b1111;
                    int c = 0;
                    for (int i = 0; i < 4; i++) {
                        if (((1 << i) & unused) > 0) {
                            p[1][c++] = i;
                        }
                    }

                    long t = 0;
                    for (int y = 0; y < n; y++) {
                        int cost1 = m - (row[0][p[y % 2][0]][y] + row[1][p[y % 2][1]][y]);
                        int cost2 = m - (row[1][p[y % 2][0]][y] + row[0][p[y % 2][1]][y]);
                        flagsR[y] = cost1 > cost2;
                        t += Math.min(cost1, cost2);
                    }
                    if (t < ans) {
                        ans = t;
                        for (int i = 0; i < 4; i++) {
                            pattern[i / 2][i % 2] = p[i / 2][i % 2];
                        }
                        choice = flagsR.clone();
                        type = false;
                    }

                    t = 0;
                    for (int x = 0; x < m; x++) {
                        int cost1 = n - (col[0][p[x % 2][0]][x] + col[1][p[x % 2][1]][x]);
                        int cost2 = n - (col[1][p[x % 2][0]][x] + col[0][p[x % 2][1]][x]);
                        flagsC[x] = cost1 > cost2;
                        t += Math.min(cost1, cost2);
                    }
                    if (t < ans) {
                        ans = t;
                        for (int i = 0; i < 4; i++) {
                            pattern[i / 2][i % 2] = p[i / 2][i % 2];
                        }
                        choice = flagsC.clone();
                        type = true;
                    }
                }
            }
            for (int y = 0; y < n; y++) {
                for (int x = 0; x < m; x++) {
                    if (!type) {
                        out.print(intToChar(pattern[y % 2][(choice[y] ? x + 1 : x) % 2]));
                    } else {
                        out.print(intToChar(pattern[x % 2][(choice[x] ? y + 1 : y) % 2]));
                    }
                }
                out.ln();
            }
            //System.out.println(type);
            //System.out.println(Arrays.deepToString(pattern));
            //System.out.println(ans);
        }

        private static char intToChar(int i) {
            return DNA[i];
        }

        private static int charToInt(char c) {
            switch (c) {
                case 'A':
                    return 0;
                case 'C':
                    return 1;
                case 'G':
                    return 2;
                case 'T':
                    return 3;
            }
            throw new IllegalArgumentException();
        }

    }

    static class LightScanner {
        private BufferedReader reader = null;
        private StringTokenizer tokenizer = null;

        public LightScanner(InputStream in) {
            reader = new BufferedReader(new InputStreamReader(in));
        }

        public String string() {
            if (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new UncheckedIOException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public int ints() {
            return Integer.parseInt(string());
        }

    }

    static class LightWriter implements AutoCloseable {
        private final Writer out;
        private boolean autoflush = false;
        private boolean breaked = true;

        public LightWriter(Writer out) {
            this.out = out;
        }

        public LightWriter(OutputStream out) {
            this(new BufferedWriter(new OutputStreamWriter(out, Charset.defaultCharset())));
        }

        public LightWriter print(char c) {
            try {
                out.write(c);
                breaked = false;
            } catch (IOException ex) {
                throw new UncheckedIOException(ex);
            }
            return this;
        }

        public LightWriter print(String s) {
            try {
                out.write(s, 0, s.length());
                breaked = false;
            } catch (IOException ex) {
                throw new UncheckedIOException(ex);
            }
            return this;
        }

        public LightWriter ln() {
            breaked = true;
            print(System.lineSeparator());
            if (autoflush) {
                try {
                    out.flush();
                } catch (IOException ex) {
                    throw new UncheckedIOException(ex);
                }
            }
            return this;
        }

        public void close() {
            try {
                out.close();
            } catch (IOException ex) {
                throw new UncheckedIOException(ex);
            }
        }

    }
}

