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

public class Main {
    void solve() {
         n=ni();m=ni();
        int s[][]=new int[n+1][m+1];
        for(int i=1;i<=n;i++){
            char s1[]=ns().toCharArray();
            for(int j=1;j<=m;j++){
                if(s1[j-1]=='A') s[i][j]=0;
                else if(s1[j-1]=='G') s[i][j]=1;
                else if(s1[j-1]=='C') s[i][j]=2;
                else s[i][j]=3;
            }
        }
       c=new int[2][2];
        ans=new int[n+1][m+1];

        solve(s);
         //c[1][1]=0; c[1][0]=1; c[0][1]=2; c[0][0]=3;
        // solveDp(s);
        String b[]={"A","G","C","T"};
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++) pw.print(b[ans[i][j]]);
            pw.println("");
        }
     //   pw.println(cost);


    }
    int n,m;
    int c[][];
    int ans[][];
    int cost=Integer.MAX_VALUE;
    int cc[][];
    int dp[][];
    void solve(int s[][]){

        for(int i=0;i<24;i++){
            c[0][0]=a[i][0];
            c[0][1]=a[i][1];
            c[1][0]=a[i][2];
            c[1][1]=a[i][3];
            solveDp(s);
           solveDp2(s);
        }

    }
    void solveDp(int s[][]){
        cc=new int[n+1][2];
        dp=new int[n+1][2];
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++) {
                if(s[i][j]!=c[i%2][j%2]) cc[i][0]++;
                if(s[i][j]!=c[i%2][1-j%2]) cc[i][1]++;
            }
          //  pw.println(cc[i][0]+" "+cc[i][1]);
        }

        for(int i=1;i<=n;i++){
            dp[i][0]=cc[i][0]+Math.min(dp[i-1][0],dp[i-1][1]);
            dp[i][1]=cc[i][1]+Math.min(dp[i-1][0],dp[i-1][1]);
        }
        int mn=Math.min(dp[n][0],dp[n][1]);
       // if(mn==0) pw.println(c[1][1]+" "+c[1][0]+" "+c[0][1]+" "+c[0][0]);
        if(mn<cost){
            cost=mn;
            int ii=n,d=-1;
            if(dp[n][0]==mn) d=0;
            else d=1;
            while(ii>0){
                if(d==0){
                    for(int j=1;j<=m;j++){
                        ans[ii][j]=c[ii%2][j%2];
                    }
                }else {
                    for(int j=1;j<=m;j++){
                        ans[ii][j]=c[ii%2][1-j%2];
                    }
                }
                if(dp[ii][d]-cc[ii][d]==dp[ii-1][0]) d=0;
                else d=1;
                ii--;

            }

        }

    }

    void solveDp2(int s[][]){
        cc=new int[m+1][2];
        dp=new int[m+1][2];
        for(int j=1;j<=m;j++){
            for(int i=1;i<=n;i++){
                if(s[i][j]!=c[j%2][i%2]) cc[j][0]++;
                if(s[i][j]!=c[j%2][1-i%2]) cc[j][1]++;
            }
        }

        for(int j=1;j<=m;j++){
            dp[j][0]=cc[j][0]+Math.min(dp[j-1][0],dp[j-1][1]);
            dp[j][1]=cc[j][1]+Math.min(dp[j-1][0],dp[j-1][1]);

        }
        int mn=Math.min(dp[m][0],dp[m][1]);
        if(mn<cost){
            cost=mn;
            int jj=m,d=-1;
            if(dp[m][0]==mn)d=0;
            else d=1;
            while(jj>0){
                if(d==0){
                    for(int i=1;i<=n;i++){
                        ans[i][jj]=c[jj%2][i%2];
                    }
                }else {
                    for(int i=1;i<=n;i++){
                        ans[i][jj]=c[jj%2][1-i%2];
                    }
                }
                if(dp[jj][d]-cc[jj][d]==dp[jj-1][0]) d=0;
                else d=1;
                jj--;
            }
        }

    }

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





    long M= (long)1e9+7;
    InputStream is;
    PrintWriter pw;
    String INPUT = "";
    void run() throws Exception {
        is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
        pw = new PrintWriter(System.out);
        long s = System.currentTimeMillis();
        solve();
        pw.flush();
        if(!INPUT.isEmpty())tr(System.currentTimeMillis()-s+"ms");

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

    private byte[] inbuf = new byte[1024];
    public int lenbuf = 0, ptrbuf = 0;

    private int readByte() {
        if(lenbuf == -1)throw new InputMismatchException();
        if(ptrbuf >= lenbuf){
            ptrbuf = 0;
            try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); }
            if(lenbuf <= 0)return -1;
        }
        return inbuf[ptrbuf++];
    }

    private boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); }
    private int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; }

    private double nd() { return Double.parseDouble(ns()); }
    private char nc() { return (char)skip(); }

    private String ns() {
        int b = skip();
        StringBuilder sb = new StringBuilder();
        while(!(isSpaceChar(b))){ // when nextLine, (isSpaceChar(b) && b != ' ')
            sb.appendCodePoint(b);
            b = readByte();
        }
        return sb.toString();
    }

    private char[] ns(int n) {
        char[] buf = new char[n];
        int b = skip(), p = 0;
        while(p < n && !(isSpaceChar(b))){
            buf[p++] = (char)b;
            b = readByte();
        }
        return n == p ? buf : Arrays.copyOf(buf, p);
    }

    private char[][] nm(int n, int m) {
        char[][] map = new char[n][];
        for(int i = 0;i < n;i++)map[i] = ns(m);
        return map;
    }

    private int[] na(int n) {
        int[] a = new int[n];
        for(int i = 0;i < n;i++)a[i] = ni();
        return a;
    }

    private int ni() {
        int num = 0, b;
        boolean minus = false;
        while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
        if(b == '-'){
            minus = true;
            b = readByte();
        }

        while(true){
            if(b >= '0' && b <= '9'){
                num = num * 10 + (b - '0');
            }else{
                return minus ? -num : num;
            }
            b = readByte();
        }
    }

    private long nl() {
        long num = 0;
        int b;
        boolean minus = false;
        while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
        if(b == '-'){
            minus = true;
            b = readByte();
        }

        while(true){
            if(b >= '0' && b <= '9'){
                num = num * 10 + (b - '0');
            }else{
                return minus ? -num : num;
            }
            b = readByte();
        }
    }
    private boolean oj = System.getProperty("ONLINE_JUDGE") != null;
    private void tr(Object... o) { if(INPUT.length() > 0)System.out.println(Arrays.deepToString(o)); }

}