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 {
	static int n,m;
	static String[] s=new String[312345];
	static String[] s1=new String[312345];
	static String[] s2=new String[312345];
	static boolean flag=false;
	static int res=-1;
	static char[] al= {'A','T','C','G'};
	static String go(String s,char c1,char c2) {
		String t1=new String();
		String t2=new String();
		StringBuilder tt1=new StringBuilder();
		StringBuilder tt2=new StringBuilder();
		for (int i=0;i<s.length();i+=2) {
			tt1.append(c1);
			if (i+1<s.length()) tt1.append(c2);
			tt2.append(c2);
			if (i+1<s.length()) tt2.append(c1);
		}
		t1=tt1+"";
		t2=tt2+"";
		if (check(s,t1)<check(s,t2)) return t1;
		return t2;
	}
	static int check(String s1,String s2) {
		int ret=0;
		for (int i=0;i<s1.length();++i)
			if (s1.charAt(i)!=s2.charAt(i))
				++ret;
		return ret;
	}
	static void solve1(char c1,char c2) {
		char c3=0,c4=0;
		String[] t=new String[312345];
		for (int i=0;i<n;++i) t[i]=new String();
		int tmp=0;
		for (int i=0;i<4;++i) if (al[i]!=c1&&al[i]!=c2)
			c3=al[i];
		for (int i=0;i<4;++i) if (al[i]!=c1&&al[i]!=c2&&al[i]!=c3)
			c4=al[i];
		for (int i=0;i<n;++i) {
			if (i%2==0) {
				t[i]=go(s[i],c1,c2);
				//System.out.println(t[i]);
				//System.out.println(s[i]);
				tmp+=check(t[i],s[i]);
			} else {
				t[i]=go(s[i],c3,c4);
				tmp+=check(t[i],s[i]);
			}
			if (res!=-1&&tmp>=res) return;
		}
		if (res==-1||tmp<res) {
			res=tmp;
			flag=false;
			for (int i=0;i<n;++i)
				s1[i]=t[i];
		}
		//System.out.println(1);
	}
	static void solve2(char c1,char c2) {
		char c3=0,c4=0;
		String[] t=new String[312345];
		for (int i=0;i<n;++i) t[i]=new String();
		int tmp=0;
		for (int i=0;i<4;++i) if (al[i]!=c1&&al[i]!=c2)
			c3=al[i];
		for (int i=0;i<4;++i) if (al[i]!=c1&&al[i]!=c2&&al[i]!=c3)
			c4=al[i];
		for (int i=0;i<m;++i) {
			StringBuilder ttt=new StringBuilder();
			for (int j=0;j<n;++j) ttt.append(s[j].charAt(i));
			String tt=new String(ttt);
			if (i%2==0) {
				t[i]=go(tt,c1,c2);
				tmp+=check(t[i],tt);
			} else {
				t[i]=go(tt,c3,c4);
				tmp+=check(t[i],tt);
			}
			if (res!=-1&&tmp>=res) return;
		}
		//System.out.println(22);
		if (res==-1||tmp<res) {
			res=tmp;
			flag=true;
			//System.out.printf("res=%d %c %c\n",res,c1,c2);
			//for (int i=0;i<m;++i)
			//	System.out.println(t[i]);
			for (int i=0;i<n;++i) {
				StringBuilder ttt=new StringBuilder();
				for (int j=0;j<m;++j)
					ttt.append(t[j].charAt(i));
				//System.out.println(ttt);
				s2[i]=ttt+"";
			}
		}
		//System.out.println(2);
	}
	public static void main(String[] args) throws IOException {
		//Scanner in=new Scanner(System.in);
		//n=150000;
		//m=2;
		//for (int i=0;i<n;++i)
		//	s[i]=new String("AA");
		//n=in.nextInt();
		//m=in.nextInt();
		//for (int i=0;i<n;++i)
		//	s[i]=in.next();
		StreamTokenizer in=new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
		PrintWriter out=new PrintWriter(new OutputStreamWriter(System.out));
		in.nextToken();
		n=(int)in.nval;
		in.nextToken();
		m=(int)in.nval;
		for (int i=0;i<n;++i) {
			in.nextToken();
			s[i]=in.sval;
		}
		//if (n==150000) return;
		solve1('A','C');
		solve2('A','C');
		solve1('A','G');
		solve2('A','G');
		solve1('A','T');
		solve2('A','T');
		solve1('G','C');
		solve2('G','C');
		solve1('G','T');
		solve2('G','T');
		solve1('C','T');
		solve2('C','T');
		//System.out.printf("%b\n",flag);
		for (int i=0;i<n;++i)
			if (flag) out.println(s2[i]);
			else out.println(s1[i]);
		out.flush();
			//if (flag) System.out.println(s2[i]);
			//else System.out.println(s1[i]);
	}
}