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

/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */

/**
 *
 * @author Andy Phan
 */
public class p1098b {
    static char[] arr = {'A', 'G', 'C', 'T'};
    public static void main(String[] args) {
        JS in = new JS();
        PrintWriter out = new PrintWriter(System.out);
        int n = in.nextInt();
        int m = in.nextInt();
        char[][] grid = new char[n][];
        for(int i = 0; i < n; i++) grid[i] = in.next().toCharArray();
        char[][] ret = new char[n][m];
        int num = n*m;
        for(int i = 0; i < 3; i++) for(int j = i+1; j < 4; j++) {
            char[] newArr = new char[4];
            newArr[0] = arr[i];
            newArr[1] = arr[j];
            if(i != 0) newArr[2] = arr[0];
            else if(j != 1) newArr[2] = arr[1];
            else newArr[2] = arr[2];
            for(int k = 0; k < 4; k++) if(k != i && k != j && arr[k] != newArr[2]) newArr[3] = arr[k];
            char[][] tmp = new char[n][];
            int tot = 0;
            for(int x = 0; x < n; x++) {
                int num0 = 0;
                int num1 = 0;
                char[] row0 = new char[m];
                char[] row1 = new char[m];
                for(int y = 0; y < m; y++) {
                    row0[y] = newArr[((x&1)<<1)+(y&1)];
                    row1[y] = newArr[((x&1)<<1)+1-(y&1)];
                    if(row0[y] != grid[x][y]) num0++;
                    if(row1[y] != grid[x][y]) num1++;
                }
                if(num0 < num1) {
                    tmp[x] = row0;
                    tot += num0;
                } else {
                    tmp[x] = row1;
                    tot += num1;
                }
            }
            if(tot < num) {
                ret = tmp;
                num = tot;
            }
        }
        
        for(int i = 0; i < 3; i++) for(int j = i+1; j < 4; j++) {
            char[] newArr = new char[4];
            newArr[0] = arr[i];
            newArr[1] = arr[j];
            if(i != 0) newArr[2] = arr[0];
            else if(j != 1) newArr[2] = arr[1];
            else newArr[2] = arr[2];
            for(int k = 0; k < 4; k++) if(k != i && k != j && arr[k] != newArr[2]) newArr[3] = arr[k];
            char[][] tmp = new char[m][];
            int tot = 0;
            for(int x = 0; x < m; x++) {
                int num0 = 0;
                int num1 = 0;
                char[] row0 = new char[n];
                char[] row1 = new char[n];
                for(int y = 0; y < n; y++) {
                    row0[y] = newArr[((x&1)<<1)+(y&1)];
                    row1[y] = newArr[((x&1)<<1)+1-(y&1)];
                    if(row0[y] != grid[y][x]) num0++;
                    if(row1[y] != grid[y][x]) num1++;
                }
                if(num0 < num1) {
                    tmp[x] = row0;
                    tot += num0;
                } else {
                    tmp[x] = row1;
                    tot += num1;
                }
            }
            if(tot < num) {
                char[][] tmp2 = new char[n][m];
                for(int x = 0; x < n; x++) for(int y = 0; y < m; y++) tmp2[x][y] = tmp[y][x];
                ret = tmp2;
                num = tot;
            }
        }
        for(char[] a : ret) {
            out.println(new String(a));
        }
        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+(cur < 0 ? -1*nextLong()/num : 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;
		}
	}
}

}
