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.*;
import java.util.regex.*;

public class Codeforces1{
	
	static class MyScanner{
		BufferedReader br;
		StringTokenizer st;
		
		MyScanner(FileReader fileReader){
			br = new BufferedReader(fileReader);
		}
		
		MyScanner(){
			br = new BufferedReader(new InputStreamReader(System.in));
		}
		
		String nn(){
			while(st == null || !st.hasMoreElements()){
				try{
					st = new StringTokenizer(br.readLine());
				}catch(IOException e){
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}
		
		int ni(){
			return Integer.parseInt(nn());
		}
		
		long nl(){
			return Long.parseLong(nn());
		}
		
		double nd(){
			return Double.parseDouble(nn());
		}
	}
	
	private static PrintWriter out;
	
	public static void main(String[] args) throws FileNotFoundException{
		
		
		// Input from file
		// File inputFile = new File("JavaFile.txt");
		// File outputFile = new File("JavaOutputFile.txt");
		// FileReader fileReader = new FileReader(inputFile);
		// Here it ends
			
		MyScanner sc = new MyScanner();
		// MyScanner sc = new MyScanner(fileReader);
		
		out = new PrintWriter(new BufferedOutputStream(System.out)); // Output to console
		// out = new PrintWriter(new PrintStream(outputFile)); // Output to file
		
		getAns(sc);
		
		out.close();
	}
	
	private static void getAns(MyScanner sc){
		TreeMap<Integer, StringBuilder> map = new TreeMap<>();
		
		int index = 1, ans = Integer.MAX_VALUE, ansIndex = 1;
		
		int n = sc.ni(), m = sc.ni();
		char[][] ar = new char[n][m];
		for(int i = 0; i < n; i++) ar[i] = sc.nn().toCharArray();
		
		requiredChanges(ar, new char[]{'A', 'G'}, new char[]{'C', 'T'}, n, m, map, index);
		
		requiredChanges(ar, new char[]{'C', 'T'}, new char[]{'A', 'G'}, n, m, map, index);
		
		requiredChanges(ar, new char[]{'A', 'C'}, new char[]{'G', 'T'}, n, m, map, index);
		
		requiredChanges(ar, new char[]{'G', 'T'}, new char[]{'A', 'C'}, n, m, map, index);
		
		requiredChanges(ar, new char[]{'A', 'T'}, new char[]{'C', 'G'}, n, m, map, index);
		
		requiredChanges(ar, new char[]{'C', 'G'}, new char[]{'A', 'T'}, n, m, map, index);
		
		// out.println(map.firstKey());
		
		out.println(map.get(map.firstKey()));
	}
	
	private static void requiredChanges(char[][] ar, char[] first, char[] second, int n, int m, TreeMap<Integer, StringBuilder> map, int index){
		int ans = 0;
		StringBuilder sb = new StringBuilder();
		for(int i = 0; i < n; i++){
			if(i % 2 == 0){
				int temp1 = 0, temp2 = 0;
				for(int j = 0; j < m; j++) temp1 += (ar[i][j] != first[j % 2])? 1: 0;
				for(int j = 0; j < m; j++) temp2 += (ar[i][j] != first[(j % 2) ^ 1])? 1: 0;
				if(temp1 < temp2) for(int j = 0; j < m; j++) sb.append(first[j % 2]);
				else for(int j = 0; j < m; j++) sb.append(first[(j % 2) ^ 1]);
				ans += Math.min(temp1, temp2);
				sb.append("\n");
			}else{
				int temp1 = 0, temp2 = 0;
				for(int j = 0; j < m; j++) temp1 += (ar[i][j] != second[j % 2])? 1: 0;
				for(int j = 0; j < m; j++) temp2 += (ar[i][j] != second[(j % 2) ^ 1])? 1: 0;
				if(temp1 < temp2) for(int j = 0; j < m; j++) sb.append(second[j % 2]);
				else for(int j = 0; j < m; j++) sb.append(second[(j % 2) ^ 1]);
				ans += Math.min(temp1, temp2);
				sb.append("\n");
			}
		}
		map.put(ans, sb);
		newChanges(ar, first, second, n, m, map, index);
	}
	
	private static void newChanges(char[][] ar, char[] first, char[] second, int n, int m, TreeMap<Integer, StringBuilder> map, int index){
		int ans = 0;
		char[][] req = new char[n][m];
		StringBuilder sb = new StringBuilder();
		for(int i = 0; i < m; i++){
			if(i % 2 == 0){
				int temp1 = 0, temp2 = 0;
				for(int j = 0; j < n; j++) temp1 += (ar[j][i] != first[j % 2])? 1: 0;
				for(int j = 0; j < n; j++) temp2 += (ar[j][i] != first[(j % 2) ^ 1])? 1: 0;
				if(temp1 < temp2) for(int j = 0; j < n; j++) req[j][i] = first[j % 2];
				else for(int j = 0; j < n; j++) req[j][i] = first[(j % 2) ^ 1];
				ans += Math.min(temp1, temp2);
			}else{
				int temp1 = 0, temp2 = 0;
				for(int j = 0; j < n; j++) temp1 += (ar[j][i] != second[j % 2])? 1: 0;
				for(int j = 0; j < n; j++) temp2 += (ar[j][i] != second[(j % 2) ^ 1])? 1: 0;
				if(temp1 < temp2) for(int j = 0; j < n; j++) req[j][i] = second[j % 2];
				else for(int j = 0; j < n; j++) req[j][i] = second[(j % 2) ^ 1];
				ans += Math.min(temp1, temp2);
			}
		}
		
		for(int i = 0; i < n; i++){
			for(int j = 0; j < m; j++) sb.append(req[i][j]);
			sb.append("\n");
		}
		
		map.put(ans, sb);
	}
}