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 CF1098B {
	static int hamming(char[] aa, char[] bb, int m) {
		int d = 0;
		for (int j = 0; j < m; j++)
			if (aa[j] != bb[j])
				d++;
		return d;
	}
	static int greedy(char[] aa, char[] bb, int m, char a, char c, boolean fix) {
		for (int j = 0; j < m; j++)
			bb[j] = j % 2 == 0 ? a : c;
		int d0 = hamming(aa, bb, m);
		for (int j = 0; j < m; j++)
			bb[j] = j % 2 == 1 ? a : c;
		int d1 = hamming(aa, bb, m);
		if (d1 <= d0)
			return d1;
		if (fix)
			for (int j = 0; j < m; j++)
				bb[j] = j % 2 == 0 ? a : c;
		return d0;
	}
	static int greedy(char[][] aa, char[][] bb, int n, int m, char a, char c, char g, char t, boolean fix) {
		int d0 = 0;
		for (int i = 0; i < n; i++)
			d0 += i % 2 == 0 ? greedy(aa[i], bb[i], m, a, c, false) : greedy(aa[i], bb[i], m, g, t, false);
		int d1 = 0;
		for (int i = 0; i < n; i++)
			d1 += i % 2 == 1 ? greedy(aa[i], bb[i], m, a, c, fix) : greedy(aa[i], bb[i], m, g, t, fix);
		if (d1 <= d0)
			return d1;
		if (fix) {
			d0 = 0;
			for (int i = 0; i < n; i++)
				d0 += i % 2 == 0 ? greedy(aa[i], bb[i], m, a, c, true) : greedy(aa[i], bb[i], m, g, t, true);
		}
		return d0;
	}
	static void transpose(char[][] xy, char[][] yx, int n, int m) {
		for (int i = 0; i < n; i++)
			for (int j = 0; j < m; j++)
				yx[j][i] = xy[i][j];
	}
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter pw = new PrintWriter(System.out);
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		char[][] xy = new char[n][m];
		char[][] xy_ = new char[n][m];
		for (int i = 0; i < n; i++)
			br.readLine().getChars(0, m, xy[i], 0);
		char[][] yx = new char[m][n];
		char[][] yx_ = new char[m][n];
		transpose(xy, yx, n, m);
		int xy_ac_gt = greedy(xy, xy_, n, m, 'A', 'C', 'G', 'T', false);
		int xy_ag_ct = greedy(xy, xy_, n, m, 'A', 'G', 'C', 'T', false);
		int xy_at_cg = greedy(xy, xy_, n, m, 'A', 'T', 'C', 'G', false);
		int yx_ac_gt = greedy(yx, yx_, m, n, 'A', 'C', 'G', 'T', false);
		int yx_ag_ct = greedy(yx, yx_, m, n, 'A', 'G', 'C', 'T', false);
		int yx_at_cg = greedy(yx, yx_, m, n, 'A', 'T', 'C', 'G', false);
		int xy_min = Math.min(xy_ac_gt, Math.min(xy_ag_ct, xy_at_cg));
		int yx_min = Math.min(yx_ac_gt, Math.min(yx_ag_ct, yx_at_cg));
		if (xy_min <= yx_min) {
			if (xy_min == xy_ac_gt)
				greedy(xy, xy_, n, m, 'A', 'C', 'G', 'T', true);
			else if (xy_min == xy_ag_ct)
				greedy(xy, xy_, n, m, 'A', 'G', 'C', 'T', true);
			else
				greedy(xy, xy_, n, m, 'A', 'T', 'C', 'G', true);
		} else {
			if (yx_min == yx_ac_gt)
				greedy(yx, yx_, m, n, 'A', 'C', 'G', 'T', true);
			else if (yx_min == yx_ag_ct)
				greedy(yx, yx_, m, n, 'A', 'G', 'C', 'T', true);
			else
				greedy(yx, yx_, m, n, 'A', 'T', 'C', 'G', true);
			transpose(yx_, xy_, m, n);
		}
		for (int i = 0; i < n; i++)
			pw.println(xy_[i]);
		pw.close();
	}
}
