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.StringTokenizer;
public class Main {
    private static char[] table = {'A', 'G', 'T', 'C'};
    public static void main(String[] args) {
        FastScanner sc = new FastScanner(System.in);
        PrintWriter out = new PrintWriter(System.out);
        int N = sc.nextInt();
        int M = sc.nextInt();
        int maxMatches = -1;
        int bestT = -1;
        char[][] arr = new char[N][];
        for (int i = 0; i < N; i++)
            arr[i] = sc.next().toCharArray();
        char[][] nice = null;
        for (int t = 0; t < 2; t++) {
            int[] a = new int[N];
            for (int c1 = 0; c1 < 4; c1++) {
                for (int c2 = c1 + 1; c2 < 4; c2++) {
                    int c3 = 0;
                    while (c3 == c1 || c3 == c2) c3++;
                    int c4 = c3 + 1;
                    while (c4 == c2 || c4 == c1) c4++;
                    char[] chars = new char[4];
                    chars[0] = table[c1];
                    chars[1] = table[c2];
                    chars[2] = table[c3];
                    chars[3] = table[c4];
                    int count = 0;
                    for (int n = 0; n < N; n++) {
                        int b = (n & 1) << 1;
                        int maxAns = -1;
                        int tmp = -1;
                        for (int c = 0; c < 2; c++) {
                            int now = 0;
                            for (int m = 0; m < M; m++)
                                if (arr[n][m] == chars[b + ((m & 1) ^ c)]) now++;
                            if (now > maxAns) {
                                maxAns = now;
                                tmp = c;
                            }
                        }
                        count += maxAns;
                        a[n] = tmp;
                    }                        
                    if (count > maxMatches) {
                        maxMatches = count;
                        bestT = t;
                        nice = new char[N][M];
                        for (int i = 0; i < N; i++) {
                            int b = (i & 1) << 1;
                            int tmp = a[i];
                            for (int j = 0; j < M; j++) {
                                nice[i][j] = chars[b + ((j & 1) ^ tmp)];
                            }
                        }
                    }
                }
            }
                    
            char[][] newArr = transpose(arr, N, M);
            int tmp = N;
            N = M;
            M = tmp;
            arr = newArr;
        }
        if (bestT == 1) {
            nice = transpose(nice, M, N);
        }
        for (int k = 0; k < N; k++)
            out.println(new String(nice[k]));
        out.close();
    }
    private static char[][] transpose(char[][] arr, int N, int M) {
        char[][] newArr = new char[M][N];
        for (int i = 0; i < M; i++)
            for (int j = 0; j < N; j++)
                newArr[i][j] = arr[j][i];
        return newArr;
    }


        
    static class FastScanner {
        private BufferedReader reader = null;
        private StringTokenizer tokenizer = null;
        
        public FastScanner(InputStream in) {
            reader = new BufferedReader(new InputStreamReader(in));
            tokenizer = null;
        }
        
        public String next() {
            if (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }
        
        public String nextLine() {
            if (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    return reader.readLine();
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken("\n");
        }
        
  /*      public long nextLong() {
            return Long.parseLong(next());
        }
        */
        public int nextInt() {
            return Integer.parseInt(next());
        }
        
       /* public double nextDouble() {
            return Double.parseDouble(next());
        }
        
        public int[] nextIntArray(int n) {
            int[] a = new int[n];
            for (int i = 0; i < n; ++i) {
                a[i] = nextInt();
            }
            return a;
        }
        
        public long[] nextLongArray(int n) {
            long[] a = new long[n];
            for (int i = 0; i < n; i++) {
                a[i] = nextLong();
            }
            return a;
        }*/
    }
}