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.*;

public class B implements Runnable {
	public static void main (String[] args) {new Thread(null, new B(), "_cf", 1 << 28).start();}
	
	int n, m, TYPES = 12;
	int[][] costs;
	boolean[][] valid;
	int[][] dp, build;
	
	public void run() {
		FastScanner fs = new FastScanner();
		PrintWriter out = new PrintWriter(System.out);
		System.err.println("Go!");

		n = fs.nextInt();
		m = fs.nextInt();
		char[][] g = new char[n][];
		for(int i = 0; i < n; i++) g[i] = fs.next().toCharArray();
		costs = new int[TYPES][n];
		
		char[] letters = {'A', 'C', 'G', 'T'};
		String[] them = new String[TYPES];
		for(int i = 0; i < TYPES; i++) {
			int fi = i / 3;
			int cnt = i % 3;
			int se = -1, ct = 0;
			for(int j = 0; j < 4; j++) if(j != fi) {
				if(ct == cnt) {
					se = j;
					break;
				}
				else ct++;
			}
			them[i] = letters[fi]+""+letters[se];
		}
		
		valid = new boolean[TYPES][TYPES];
		for(int i = 0; i < TYPES; i++) {
			for(int j = 0; j < TYPES; j++) {
				int mask = 0;
				for(char c : them[i].toCharArray()) mask |= (1 << (c-'A'));
				for(char c : them[j].toCharArray()) mask |= (1 << (c-'A'));
				if(Integer.bitCount(mask) == 4) {
					valid[i][j] = true;
				}
			}
		}
		
		for(int i = 0; i < n; i++) {
			for(int msk = 0; msk < TYPES; msk++) {
				for(int j = 0; j < g[i].length; j++) {
					if(j % 2 == 0) {
						if(g[i][j] != them[msk].charAt(0)) costs[msk][i]++;
					}
					else {
						if(g[i][j] != them[msk].charAt(1)) costs[msk][i]++;
					}
				}
			}
		}
		
		dp = new int[TYPES][n];
		build = new int[TYPES][n];
		for(int[] x : dp) Arrays.fill(x, -1);
		int resRow = oo;
		int firstRow = -1;
		for(int i = 0; i < TYPES; i++) {
			int ret = solve(i, 1) + costs[i][0];
			if(ret < resRow) {
				resRow = ret;
				firstRow = i;
			}
		}
		
		//maybe do by columns also
		int[][] bRow = new int[TYPES][n];
		for(int i = 0; i < TYPES; i++) bRow[i] = build[i].clone();
		
		costs = new int[TYPES][m];
		dp = new int[TYPES][m];
		for(int[] x : dp) Arrays.fill(x, -1);
		build = new int[TYPES][m];
		for(int j = 0; j < m; j++) {
			for(int msk = 0; msk < TYPES; msk++) {
				for(int i = 0; i < n; i++) {
					if(i % 2 == 0 ) {
						if(g[i][j] != them[msk].charAt(0)) costs[msk][j]++;
					}
					else {
						if(g[i][j] != them[msk].charAt(1)) costs[msk][j]++;
					}
				}
			}
		}
		int resCol = oo, firstCol = -1;
		for(int i = 0; i < TYPES; i++) {
			int ret = solve(i, 1) + costs[i][0];
			if(ret < resCol) {
				resCol = ret;
				firstCol = i;
			}
		}
		
		char[][] res = new char[n][m];
		if(resCol < resRow) {
			for(int i = 0; i < n; i++) {
				res[i][0] = them[firstCol].charAt(i%2);
			}
			firstCol = build[firstCol][1];
			for(int j = 1; j < m; j++) {
				for(int i = 0; i < n; i++) {
					res[i][j] = them[firstCol].charAt(i%2);
				}
				if(j < m-1) firstCol = build[firstCol][j+1];
			}
			
		}
		else {
			for(int j = 0; j < m; j++) {
				res[0][j] = them[firstRow].charAt(j%2);
			}
			firstRow = bRow[firstRow][1];
			for(int i = 1; i < n; i++) {
				for(int j = 0; j < m; j++) {
					res[i][j] = them[firstRow].charAt(j%2);
				}
				if(i < n-1) firstRow = bRow[firstRow][i+1];
			}
			
		}
		
		for(int i = 0; i < n; i++) {
			out.println(new String(res[i]));
		}
		
//		System.out.println(resRow + " " + resCol);
//		System.out.println(them[firstRow] + " " + them[firstCol]);
		
		out.close();
	}
	
	int oo = (int)2e9;
	int solve(int msk, int row) {
		if(row == dp[0].length) return 0;
		int ret = dp[msk][row];
		if(ret != -1) return ret;
		ret = oo;
		for(int next = 0; next < TYPES; next++) if(valid[msk][next]) {
			int get = solve(next, row+1);
			if(get == oo) continue;
			get += costs[next][row];
			if(get < ret) {
				ret = get;
				build[msk][row] = next;
			}
		}
		return dp[msk][row] = ret;
	}
	
	int find(char[] g, char x) {
		for(int i = 0; i <g.length; i++) if(g[i] == x) return i;
		return -1;
	}
	
	class FastScanner {
		public int BS = 1<<16;
		public char NC = (char)0;
		byte[] buf = new byte[BS];
		int bId = 0, size = 0;
		char c = NC;
		double num = 1;
		BufferedInputStream in;

		public FastScanner() {
			in = new BufferedInputStream(System.in, BS);
		}

		public FastScanner(String s) throws FileNotFoundException {
			in = new BufferedInputStream(new FileInputStream(new File(s)), BS);
		}

		public char nextChar(){
			while(bId==size) {
				try {
					size = in.read(buf);
				}catch(Exception e) {
					return NC;
				}                
				if(size==-1)return NC;
				bId=0;
			}
			return (char)buf[bId++];
		}

		public int nextInt() {
			return (int)nextLong();
		}

		public long nextLong() {
			num=1;
			boolean neg = false;
			if(c==NC)c=nextChar();
			for(;(c<'0' || c>'9'); c = nextChar()) {
				if(c=='-')neg=true;
			}
			long res = 0;
			for(; c>='0' && c <='9'; c=nextChar()) {
				res = (res<<3)+(res<<1)+c-'0';
				num*=10;
			}
			return neg?-res:res;
		}

		public double nextDouble() {
			double cur = nextLong();
			return c!='.' ? cur:cur+nextLong()/num;
		}

		public String next() {
			StringBuilder res = new StringBuilder();
			while(c<=32)c=nextChar();
			while(c>32) {
				res.append(c);
				c=nextChar();
			}
			return res.toString();
		}

		public String nextLine() {
			StringBuilder res = new StringBuilder();
			while(c<=32)c=nextChar();
			while(c!='\n') {
				res.append(c);
				c=nextChar();
			}
			return res.toString();
		}

		public boolean hasNext() {
			if(c>32)return true;
			while(true) {
				c=nextChar();
				if(c==NC)return false;
				else if(c>32)return true;
			}
		}
		
		public int[] nextIntArray(int n) {
			int[] res = new int[n];
			for(int i = 0; i < n; i++) res[i] = nextInt();
			return res;
		}
		
	}

	
}