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.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.io.PrintWriter;
public class B1098 
{
    static class Scanner
    {
        BufferedReader br;
        StringTokenizer tk=new StringTokenizer("");
        public Scanner(InputStream is) 
        {
            br=new BufferedReader(new InputStreamReader(is));
        }
        public int nextInt() throws IOException
        {
            if(tk.hasMoreTokens())
                return Integer.parseInt(tk.nextToken());
            tk=new StringTokenizer(br.readLine());
            return nextInt();
        }
        public long nextLong() throws IOException
        {
            if(tk.hasMoreTokens())
                return Long.parseLong(tk.nextToken());
            tk=new StringTokenizer(br.readLine());
            return nextLong();
        }
        public String next() throws IOException
        {
            if(tk.hasMoreTokens())
                return (tk.nextToken());
            tk=new StringTokenizer(br.readLine());
            return next();
        }
        public String nextLine() throws IOException
        {
            tk=new StringTokenizer("");
            return br.readLine();
        }
        public double nextDouble() throws IOException
        {
            if(tk.hasMoreTokens())
                return Double.parseDouble(tk.nextToken());
            tk=new StringTokenizer(br.readLine());
            return nextDouble();
        }
        public char nextChar() throws IOException
        {
            if(tk.hasMoreTokens())
                return (tk.nextToken().charAt(0));
            tk=new StringTokenizer(br.readLine());
            return nextChar();
        }
        public int[] nextIntArray(int n) throws IOException
        {
            int a[]=new int[n];
            for(int i=0;i<n;i++)
                a[i]=nextInt();
            return a;
        }
        public long[] nextLongArray(int n) throws IOException
        {
            long a[]=new long[n];
            for(int i=0;i<n;i++)
                a[i]=nextLong();
            return a;
        }
        public int[] nextIntArrayOneBased(int n) throws IOException
        {
            int a[]=new int[n+1];
            for(int i=1;i<=n;i++)
                a[i]=nextInt();
            return a;
        }
        public long[] nextLongArrayOneBased(int n) throws IOException
        {
            long a[]=new long[n+1];
            for(int i=1;i<=n;i++)
                a[i]=nextLong();
            return a;
        }
    
    
    }
    static int n,m;
    static char c[][];
    static char ans[][];
    static int ansv=Integer.MAX_VALUE;
    static void sr(char c1[],char c2[])
    {
        char re1[]=new char[m];
        char re2[]=new char[m];
        char ro1[]=new char[m];
        char ro2[]=new char[m];
        for(int i=0;i<m;i++)
        {
            re1[i]=c1[i%2];
            re2[i]=c1[(i+1)%2];
            ro1[i]=c2[i%2];
            ro2[i]=c2[(i+1)%2];
        }
        char s[][]=new char[n][m];
        int su=0;
        for(int i=0;i<n;i++)
        {
           if(su>=ansv)
               return;
            if(i%2==0)
            {
                int s1=0,s2=0;
                for(int j=0;j<m;j++)
                {
                    if(c[i][j]!=re1[j])
                        s1++;
                    if(c[i][j]!=re2[j])
                        s2++;
                }
                su+=Math.min(s1,s2);
                if(s1<s2)
                    System.arraycopy(re1, 0, s[i], 0, m);
                else
                    System.arraycopy(re2, 0, s[i], 0, m);
            }
            else
            {
                int s1=0,s2=0;
                for(int j=0;j<m;j++)
                {
                    if(c[i][j]!=ro1[j])
                        s1++;
                    if(c[i][j]!=ro2[j])
                        s2++;
                }
                su+=Math.min(s1,s2);
                if(s1<s2)
                    System.arraycopy(ro1, 0, s[i], 0, m);
                else
                    System.arraycopy(ro2, 0, s[i], 0, m);
            }
        }
        if(su>=ansv)
            return;
        ansv=su;
        for(int i=0;i<n;i++)
            System.arraycopy(s[i], 0, ans[i], 0, m);
    }
    static void sc(char c1[],char c2[])
    {
        char ce1[]=new char[n];
        char ce2[]=new char[n];
        char co1[]=new char[n];
        char co2[]=new char[n];
        for(int i=0;i<n;i++)
        {
            ce1[i]=c1[i%2];
            ce2[i]=c1[(i+1)%2];
            co1[i]=c2[i%2];
            co2[i]=c2[(i+1)%2];
        }
        char s[][]=new char[n][m];
        int su=0;
        for(int j=0;j<m;j++)
        {
            if(su>=ansv)
                return;
            if(j%2==0)
            {
                int s1=0,s2=0;
                for(int i=0;i<n;i++)
                {
                    if(c[i][j]!=ce1[i])
                        s1++;
                    if(c[i][j]!=ce2[i])
                        s2++;
                }
                su+=Math.min(s1,s2);
                if(s1<s2)
                    for(int i=0;i<n;i++)
                        s[i][j]=ce1[i];
                else
                    for(int i=0;i<n;i++)
                        s[i][j]=ce2[i];
            }
            else
            {
                int s1=0,s2=0;
                for(int i=0;i<n;i++)
                {
                    if(c[i][j]!=co1[i])
                        s1++;
                    if(c[i][j]!=co2[i])
                        s2++;
                }
                su+=Math.min(s1,s2);
                if(s1<s2)
                    for(int i=0;i<n;i++)
                        s[i][j]=co1[i];
                else
                    for(int i=0;i<n;i++)
                        s[i][j]=co2[i];
            }
        }
        if(su>=ansv)
            return;
        ansv=su;
        for(int i=0;i<n;i++)
            System.arraycopy(s[i], 0, ans[i], 0, m);
    }
    static char c1[]={'A','G'};
    static char c2[]={'A','C'};
    static char c3[]={'A','T'};
    static char c4[]={'C','T'};
    static char c5[]={'G','T'};
    static char c6[]={'C','G'};
    public static void main(String args[]) throws IOException
    {
        Scanner in=new Scanner(System.in);
        PrintWriter out=new PrintWriter(System.out);
        n=in.nextInt();
        m=in.nextInt();
        c=new char[n][];
        ans=new char[n][m];
        for(int i=0;i<n;i++)
            c[i]=in.next().toCharArray();
        sr(c1,c4);sr(c2,c5);sr(c3,c6);sr(c4,c1);sr(c5,c2);sr(c6,c3);
        sc(c1,c4);sc(c2,c5);sc(c3,c6);sc(c4,c1);sc(c5,c2);sc(c6,c3);
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
                out.print(ans[i][j]);
            out.println();
        }    
            
        out.close();
    }

}
