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.util.*;
import java.io.*;

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

    FastReader in = new FastReader();
    PrintWriter out = new PrintWriter(System.out);
    void run() {
        work();
        out.flush();
    }

    long mod = 998244353;
    long gcd(long a, long b) {
        return a == 0 ? b : gcd(b % a, a);
    }
    long inf = Long.MAX_VALUE / 3;
    char[][] A;
    int ret=999999999;
    char[] chs={'A','G','C','T'};
    char[][] B;
    void work() {
        int n=ni(),m=ni();
        A=new char[n][m];
        for(int i=0;i<n;i++){
            String str=ns();
            for(int j=0;j<m;j++){
                A[i][j]=str.charAt(j);
            }
        }
        List<Integer> list=new ArrayList<>();
        dfs(list,new boolean[4]);
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                out.print(B[i][j]);
            }
            out.println();
        }
    }

    private void dfs(List<Integer> list, boolean[] vis) {
        if(list.size()==4){
            count1(list);
            count2(list);
            return;
        }
        for(int i=0;i<4;i++){
            if(!vis[i]){
                vis[i]=true;
                list.add(i);
                dfs(list,vis);
                list.remove(list.size()-1);
                vis[i]=false;
            }
        }
    }

    private void count2(List<Integer> list) {
        int n=A.length,m=A[0].length;
        char ch1=chs[list.get(0)];
        char ch2=chs[list.get(1)];
        char ch3=chs[list.get(2)];
        char ch4=chs[list.get(3)];
        if(ch1>ch2||ch3>ch4){
            return;
        }
        char[][] C=new char[n][m];
        int r=0;
        for(int i=0;i<n;i++){
            int c1=0,c2=0;
            if(i%2==0){
                for(int j=0;j<m;j++){
                    if(j%2==0){
                        if(ch1!=A[i][j]){
                            c1++;
                        }
                        if(ch2!=A[i][j]){
                            c2++;
                        }
                    }else{
                        if(ch2!=A[i][j]){
                            c1++;
                        }
                        if(ch1!=A[i][j]){
                            c2++;
                        }
                    }
                }
            }else{
                for(int j=0;j<m;j++){
                    if(j%2==0){
                        if(ch3!=A[i][j]){
                            c1++;
                        }
                        if(ch4!=A[i][j]){
                            c2++;
                        }
                    }else{
                        if(ch4!=A[i][j]){
                            c1++;
                        }
                        if(ch3!=A[i][j]){
                            c2++;
                        }
                    }
                }
            }
            if(c1<c2){
                for(int j=0;j<m;j++){
                    if(i%2==0){
                        if(j%2==0){
                            C[i][j]=ch1;
                        }else{
                            C[i][j]=ch2;
                        }
                    }else{
                        if(j%2==0){
                            C[i][j]=ch3;
                        }else{
                            C[i][j]=ch4;
                        }
                    }
                }
            }else{
                for(int j=0;j<m;j++){
                    if(i%2==0){
                        if(j%2==1){
                            C[i][j]=ch1;
                        }else{
                            C[i][j]=ch2;
                        }
                    }else{
                        if(j%2==1){
                            C[i][j]=ch3;
                        }else{
                            C[i][j]=ch4;
                        }
                    }
                }
            }
            r+=Math.min(c1,c2);
        }
        if(r<ret){
            ret=r;
            B=C;
        }
    }

    private void count1(List<Integer> list) {
        int n=A.length,m=A[0].length;
        char ch1=chs[list.get(0)];
        char ch2=chs[list.get(1)];
        char ch3=chs[list.get(2)];
        char ch4=chs[list.get(3)];
        if(ch1>ch2||ch3>ch4){
            return;
        }
        char[][] C=new char[n][m];
        int r=0;
        for(int j=0;j<m;j++){
            int c1=0,c2=0;
            if(j%2==0){
                for(int i=0;i<n;i++){
                    if(i%2==0){
                        if(ch1!=A[i][j]){
                            c1++;
                        }
                        if(ch2!=A[i][j]){
                            c2++;
                        }
                    }else if(i%2==1){
                        if(ch2!=A[i][j]){
                            c1++;
                        }
                        if(ch1!=A[i][j]){
                            c2++;
                        }
                    }
                }
            }else{
                for(int i=0;i<n;i++){
                    if(i%2==0){
                        if(ch3!=A[i][j]){
                            c1++;
                        }
                        if(ch4!=A[i][j]){
                            c2++;
                        }
                    }else if(i%2==1){
                        if(ch4!=A[i][j]){
                            c1++;
                        }
                        if(ch3!=A[i][j]){
                            c2++;
                        }
                    }
                }
            }
            if(c1<c2){
                for(int i=0;i<n;i++){
                    if(j%2==0){
                        if(i%2==0){
                            C[i][j]=ch1;
                        }else{
                            C[i][j]=ch2;
                        }
                    }else{
                        if(i%2==0){
                            C[i][j]=ch3;
                        }else{
                            C[i][j]=ch4;
                        }
                    }
                }
            }else{
                for(int i=0;i<n;i++){
                    if(j%2==0){
                        if(i%2==1){
                            C[i][j]=ch1;
                        }else{
                            C[i][j]=ch2;
                        }
                    }else{
                        if(i%2==1){
                            C[i][j]=ch3;
                        }else{
                            C[i][j]=ch4;
                        }
                    }
                }
            }
            r+=Math.min(c1,c2);
        }
        if(r<ret){
            ret=r;
            B=C;
        }
    }


    private ArrayList<long[]>[] ngw(int n, int m) {
        ArrayList<long[]>[] graph = (ArrayList<long[]>[]) new ArrayList[n];
        for (int i = 0; i < n; i++) {
            graph[i] = new ArrayList<>();
        }
        for (int i = 1; i <= m; i++) {
            long s = in.nextLong() - 1, e = in.nextLong() - 1, w = in.nextLong();
            graph[(int) s].add(new long[]{e, w});
            graph[(int) e].add(new long[]{s, w});
        }
        return graph;
    }

    private ArrayList<Integer>[] ng(int n, int m) {
        ArrayList<Integer>[] graph = (ArrayList<Integer>[]) new ArrayList[n];
        for (int i = 0; i < n; i++) {
            graph[i] = new ArrayList<>();
        }
        for (int i = 1; i <= m; i++) {
            int s = in.nextInt() - 1, e = in.nextInt() - 1;
            graph[s].add(e);
//            graph[e].add(s);
        }
        return graph;
    }

    private int ni() {
        return in.nextInt();
    }

    private long nl() {
        return in.nextLong();
    }

    private String ns() {
        return in.next();
    }

    private long[] na(int n) {
        long[] A = new long[n];
        for (int i = 0; i < n; i++) {
            A[i] = in.nextLong();
        }
        return A;
    }

    private int[] nia(int n) {
        int[] A = new int[n];
        for (int i = 0; i < n; i++) {
            A[i] = in.nextInt();
        }
        return A;
    }
}

class FastReader {
    BufferedReader br;
    StringTokenizer st;

    public FastReader() {
        br = new BufferedReader(new InputStreamReader(System.in));
    }


    public String next() {
        while (st == null || !st.hasMoreElements())//回车，空行情况
        {
            try {
                st = new StringTokenizer(br.readLine());
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
        return st.nextToken();
    }

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

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