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.*;
import java.util.*;
import static java.lang.Math.*;

public class E {
    public static void main(String[] args) {
        Scanner input = new Scanner();
        StringBuilder output = new StringBuilder();

        int n = input.nextInt();
        int m = input.nextInt();
        char[][] grid = new char[n][m];

        for (int i = 0; i < n; i++) {
            grid[i] = input.next().toCharArray();
        }

        char[] letters = "ACGT".toCharArray();
        int[][] rowFirst = new int[4][n]; // evens minus odds
        int[][] rowSec = new int[4][n]; // evens minus odds
        int[][] colFirst = new int[4][m];
        int[][] colSec = new int[4][m];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (j % 2  == 0) {
                    rowFirst[index(grid[i][j])][i]++;
                } else {
                    rowSec[index(grid[i][j])][i]++;
                }
                if (i % 2 == 0) {
                    colFirst[index(grid[i][j])][j]++;
                } else {
                    colSec[index(grid[i][j])][j]++;
                }
            }
        }
        // System.err.println(Arrays.deepToString(rowFirst));
        // System.err.println(Arrays.deepToString(colFirst));

        int[][] choices = {
            {0,1,2,3},
            {0,2,1,3},
            {0,3,1,2},
            {1,2,0,3},
            {1,3,0,2},
            {2,3,0,1},
        };

        // rows
        int min = n * m + 2;
        int[] best = null;
        boolean rowBest = true;
        for (int[] choice : choices) {
            int cost = m * n;
            for (int i = 0; i < n; i++) {
                int which = 2 * (i % 2);
                cost -= max(rowFirst[choice[0 + which]][i] + rowSec[choice[1 + which]][i], rowFirst[choice[1 + which]][i] + rowSec[choice[0 + which]][i]);
            }
            if (cost < min) {
                min = cost;
                best = choice;
            }
            // System.err.println(Arrays.toString(choice) + " " + cost);
        }
        for (int[] choice : choices) {
            int cost = m * n;
            for (int i = 0; i < m; i++) {
                int which = 2 * (i % 2);
                // cost -= max(max(colValue[choice[0 + which]][j], 0) + max(-colValue[choice[1 + which]][j], 0),
                    // max(colValue[choice[1 + which]][j], 0) + max(-colValue[choice[0 + which]][j], 0));
                cost -= max(colFirst[choice[0 + which]][i] + colSec[choice[1 + which]][i], colFirst[choice[1 + which]][i] + colSec[choice[0 + which]][i]);
            }
            if (cost < min) {
                min = cost;
                best = choice;
                rowBest = false;
            }
            // System.err.println(Arrays.toString(choice) + " " + cost);
        }
        // System.err.println(rowBest);
        // System.err.println(min);
        // System.err.println(Arrays.toString(best));

        int[] choice = best;
        if (rowBest) {
            for (int i = 0; i < n; i++) {
                int which = 2 * (i % 2);
                char a = letters[choice[0 + which]];
                char b = letters[choice[1 + which]];
                if (rowFirst[choice[0 + which]][i] + rowSec[choice[1 + which]][i] < rowFirst[choice[1 + which]][i] + rowSec[choice[0 + which]][i]) {
                    b = letters[choice[0 + which]];
                    a = letters[choice[1 + which]];
                }
                for (int j = 0; j < m; j++) {
                    grid[i][j] = j % 2 == 0 ? a : b;
                }
            }
        } else {
            for (int i = 0; i < m; i++) {
                int which = 2 * (i % 2);
                char a = letters[choice[0 + which]];
                char b = letters[choice[1 + which]];
                if (colFirst[choice[0 + which]][i] + colSec[choice[1 + which]][i] < colFirst[choice[1 + which]][i] + colSec[choice[0 + which]][i]) {
                    b = letters[choice[0 + which]];
                    a = letters[choice[1 + which]];
                }
                for (int j = 0; j < n; j++) {
                    grid[j][i] = j % 2 == 0 ? a : b;
                }
            }
        }

        for (int i = 0; i < n; i++) {
            output.append(new String(grid[i]));
            output.append(System.lineSeparator());
        }

        System.out.print(output.toString());
    }

    private static int index(char c) {
        switch (c) {
            case 'A':
                return 0;
            case 'C':
                return 1;
            case 'G':
                return 2;
            case 'T':
                return 3;
        }
        return 4;
    }

    private static class Scanner {
        BufferedReader br; StringTokenizer st;
        public Scanner(Reader in) { br = new BufferedReader(in); }
        public Scanner() { this(new InputStreamReader(System.in)); }
        String next() {
            while (st == null || !st.hasMoreElements()) {
                try { st = new StringTokenizer(br.readLine());
                } catch (IOException e) { e.printStackTrace(); } }
            return st.nextToken(); }
        int nextInt() { return Integer.parseInt(next()); }
        long nextLong() { return Long.parseLong(next()); }
        double nextDouble() { return Double.parseDouble(next()); }
        String readNextLine() {
            String str = "";
            try { str = br.readLine();
            } catch (IOException e) { e.printStackTrace(); }
            return str; }
        int[] readIntArray(int n) {
            int[] a = new int[n];
            for (int idx = 0; idx < n; idx++) { a[idx] = nextInt(); }
            return a; }
        long[] readLongArray(int n) {
            long[] a = new long[n];
            for (int idx = 0; idx < n; idx++) { a[idx] = nextLong(); }
            return a; }
    } // end Scanner
}
