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.BufferedInputStream;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.PrintWriter;

public class B {
	
	int cost = Integer.MAX_VALUE;
	char[][] grid;
	int rows, cols;
	
	char[][] go1(char a, char b, char c, char d) {
		char[] even = {a, b};
		char[] odd = {c, d};
		char[][] cur = new char[rows][cols];
		cost = 0;
		for(int i = 0; i < rows; ++i) {
			char[] first = new char[cols];
			char[] second = new char[cols];
			int cost1 = 0;
			int cost2 = 0;
			{
				char[] op = i % 2 == 0 ? even : odd;
				int idx = 0;
				for(int j = 0; j < cols; ++j, idx = (idx + 1) % 2) {
					first[j] = op[idx];
					if(first[j] != grid[i][j]) ++cost1;
				}
			}
			{
				char[] op = i % 2 == 0 ? even : odd;
				int idx = 1;
				for(int j = 0; j < cols; ++j, idx = (idx + 1) % 2) {
					second[j] = op[idx];
					if(second[j] != grid[i][j]) ++cost2;
				}
			}
			char[] better = cost1 < cost2 ? first : second;
			cost += Math.min(cost1, cost2);
			for(int j = 0; j < cols; ++j) {
				cur[i][j] = better[j];
			}
		}
		return cur;
	}
	
	char[][] go2(char a, char b, char c, char d) {
		char[] even = {a, b};
		char[] odd = {c, d};
		char[][] cur = new char[rows][cols];
		cost = 0;
		for(int j = 0; j < cols; ++j) {
			char[] first = new char[rows];
			char[] second = new char[rows];
			int cost1 = 0;
			int cost2 = 0;
			{
				char[] op = j % 2 == 0 ? even : odd;
				int idx = 0;
				for(int i = 0; i < rows; ++i, idx = (idx + 1) % 2) {
					first[i] = op[idx];
					if(first[i] != grid[i][j]) ++cost1;
				}
			}
			{
				char[] op = j % 2 == 0 ? even : odd;
				int idx = 1;
				for(int i = 0; i < rows; ++i, idx = (idx + 1) % 2) {
					second[i] = op[idx];
					if(second[i] != grid[i][j]) ++cost2;
				}
			}
			char[] better = cost1 < cost2 ? first : second;
			cost += Math.min(cost1, cost2);
			for(int i = 0; i < rows; ++i) {
				cur[i][j] = better[i];
			}
		}
		return cur;
	}
	
	public void solve(JS in, PrintWriter out) {
		rows = in.nextInt();
		cols = in.nextInt();
		grid = new char[rows][cols];
		for(int r = 0; r < rows; ++r) {
			String s = in.next();
			for(int c = 0; c < cols; ++c) {
				grid[r][c] = s.charAt(c);
			}
		}
		char[] ops = "ACGT".toCharArray();
		char[][] ans = null;
		int best = Integer.MAX_VALUE;
		for(int a = 0; a < 4; ++a) {
			for(int b = a + 1; b < 4; ++b) if(a != b) {
				for(int c = 0; c < 4; ++c) if(c != a && c != b) {
					for(int d = c + 1; d < 4; ++d) if(d != a && d != b && d != c) {
						{
							char[][] cur = go1(ops[a], ops[b], ops[c], ops[d]);
							if(cost < best) {
								best = cost;
								ans = cur;
							}
						}
						{
							char[][] cur = go2(ops[a], ops[b], ops[c], ops[d]);
							if(cost < best) {
								best = cost;
								ans = cur;
							}
						}
					}
				}
			}
		}
		for(int r = 0; r < rows; ++r) {
			for(int c = 0; c < cols; ++c) {
				out.print(ans[r][c]);
			}
			out.println();
		}
//		System.err.println(best);
	}
	
	public static void main(String[] args) {
		JS in = new JS();
		PrintWriter out = new PrintWriter(System.out);
		new B().solve(in, out);
		out.close();
	}
	
	static class JS {
		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 JS() {
			in = new BufferedInputStream(System.in, BS);
		}

		public JS(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;
			}
		}
	}
}
