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.
// package PRA;

import java.io.*;
import java.math.BigInteger;
import java.util.*;

public class Main {
	public static void main(String[] arg) {
		new Main().solve();
	}
	
	StringTokenizer ST;
	BufferedReader BR;
	PrintWriter PW;
	
	String next() {
		while(ST == null || !ST.hasMoreTokens()) {
			try {
				ST = new StringTokenizer(BR.readLine());
			}catch (Exception e) {
				// TODO: handle exception
				throw new RuntimeException(e);
			}
		}
		return ST.nextToken();
	}
	
	int nextInt() {
		return Integer.parseInt(next());
	}
	
	long nextLong() {
		return Long.parseLong(next());
	}
	
	void solve() {
		BR = new BufferedReader(new InputStreamReader(System.in));
		PW = new PrintWriter(System.out);
		
		int n = nextInt(), m = nextInt();
		char[][] s = new char[n][m];
		
		for(int i = 0; i < n; i++)
			s[i] = next().toCharArray();
		
		char a[] = new String("AGCT").toCharArray();
		int R[][][] = new int[4][2][n];
		int C[][][] = new int[4][2][m];
		
		for(int l = 0; l < 4; l++)
		for(int st = 0; st < 2; st++) {
			for(int i = 0; i < n; i++)
			for(int j = st; j < m; j += 2)
				if(s[i][j] != a[l]) R[l][st][i]++;
			for(int j = 0; j < m; j++)
			for(int i = st; i < n; i += 2)
				if(s[i][j] != a[l]) C[l][st][j]++;
		}
		
		int ans = n * m + 1, flag = 0;
		int[] xx = new int[2];
		int[] yy = new int[2];
		
		int[] x = new int[2];
		int[] y = new int[2];
		for(x[0] = 0; x[0] < 4; x[0]++)
		for(y[0] = x[0] + 1; y[0] < 4; y[0]++) {
			for(int i = 0; i < 4; i++)
				if(i != x[0] && i != y[0]) {
					x[1] = i; y[1] = 6 - x[0] - y[0] - x[1];
					break;
				}
			
			int num = 0;
			for(int i = 0; i < n; i++) {
				int f = (i & 1);
				num += Math.min(R[x[f]][0][i] + R[y[f]][1][i], R[x[f]][1][i] + R[y[f]][0][i]);
			}
			
			if(num < ans) {
				ans = num;
				xx[0] = x[0]; xx[1] = x[1];
				yy[0] = y[0]; yy[1] = y[1];
			}
		}
		
		for(x[0] = 0; x[0] < 4; x[0]++)
		for(y[0] = x[0] + 1; y[0] < 4; y[0]++) {
			for(int i = 0; i < 4; i++)
				if(i != x[0] && i != y[0]) {
					x[1] = i; y[1] = 6 - x[0] - y[0] - x[1];
					break;
				}
			
			int num = 0;
			for(int i = 0; i < m; i++) {
				int f = (i & 1);
				num += Math.min(C[x[f]][0][i] + C[y[f]][1][i], C[x[f]][1][i] + C[y[f]][0][i]);
			}
			
			if(num < ans) {
				ans = num; flag = 1;
				xx[0] = x[0]; xx[1] = x[1];
				yy[0] = y[0]; yy[1] = y[1];
			}
		}
		
//		PW.println(ans + " " + flag);
		
		x[0] = xx[0]; x[1] = xx[1];
		y[0] = yy[0]; y[1] = yy[1];
		
		char TW[] = new char[2];
		if(flag == 1) {
			for(int i = 0; i < m; i++) {
				int f = (i & 1);
				if(C[x[f]][0][i] + C[y[f]][1][i] < C[x[f]][1][i] + C[y[f]][0][i]) {
					TW[0] = a[x[f]]; TW[1] = a[y[f]];
				} else {
					TW[0] = a[y[f]]; TW[1] = a[x[f]];
				}
				for(int j = 0; j < n; j++)
					s[j][i] = TW[j&1];
			}
		} else {
			for(int i = 0; i < n; i++) {
				int f = (i & 1);
				if(R[x[f]][0][i] + R[y[f]][1][i] < R[x[f]][1][i] + R[y[f]][0][i]) {
					TW[0] = a[x[f]]; TW[1] = a[y[f]];
				} else {
					TW[0] = a[y[f]]; TW[1] = a[x[f]];
				}
				for(int j = 0; j < m; j++)
					s[i][j] = TW[j&1];
			}
		}
		
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < m; j++)
				PW.print(s[i][j]);
			PW.println();
		}
		
		PW.close();
	}
}