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

public class NiceTable {

	int N, M, x, y, xx, yy;
	char grid[][], d[] = { 'A', 'G', 'C', 'T' };

	int costR(int r, int x, int y) {
		int a = 0, b = 0;
		for (int i = 0; i < M; i += 2) {
			a += grid[r][i] == d[x] ? 0 : 1;
			b += grid[r][i] == d[y] ? 0 : 1;
		}
		for (int i = 1; i < M; i += 2) {
			a += grid[r][i] == d[y] ? 0 : 1;
			b += grid[r][i] == d[x] ? 0 : 1;
		}
		return a < b ? a : b;
	}

	int bestR(int r, int x, int y) {
		int a = 0, b = 0;
		for (int i = 0; i < M; i += 2) {
			a += grid[r][i] == d[x] ? 0 : 1;
			b += grid[r][i] == d[y] ? 0 : 1;
		}
		for (int i = 1; i < M; i += 2) {
			a += grid[r][i] == d[y] ? 0 : 1;
			b += grid[r][i] == d[x] ? 0 : 1;
		}
		return a < b ? x : y;
	}

	int costC(int c, int x, int y) {
		int a = 0, b = 0;
		for (int i = 0; i < N; i += 2) {
			a += grid[i][c] == d[x] ? 0 : 1;
			b += grid[i][c] == d[y] ? 0 : 1;
		}
		for (int i = 1; i < N; i += 2) {
			a += grid[i][c] == d[y] ? 0 : 1;
			b += grid[i][c] == d[x] ? 0 : 1;
		}
		return a < b ? a : b;
	}

	int bestC(int c, int x, int y) {
		int a = 0, b = 0;
		for (int i = 0; i < N; i += 2) {
			a += grid[i][c] == d[x] ? 0 : 1;
			b += grid[i][c] == d[y] ? 0 : 1;
		}
		for (int i = 1; i < N; i += 2) {
			a += grid[i][c] == d[y] ? 0 : 1;
			b += grid[i][c] == d[x] ? 0 : 1;
		}
		return a < b ? x : y;
	}

	void solve(Scanner s, PrintWriter out) {
		N = s.nextInt();
		M = s.nextInt();
		grid = new char[N][];
		for (int i = 0; i < N; i++)
			grid[i] = s.next().toCharArray();
		int bestR = N * M, zR[] = null;
		int bestC = N * M, zC[] = null;
		for (int a = 0; a < 1 << 4; a++, x = xx = 0) {
			if (Integer.bitCount(a) != 2)
				continue;
			int[] p = p(a);
			int totR = 0, totC = 0;
			for (int r = 0; r < N; r += 2)
				totR += costR(r, x, y);
			for (int r = 1; r < N; r += 2)
				totR += costR(r, xx, yy);
			for (int c = 0; c < M; c += 2)
				totC += costC(c, x, y);
			for (int c = 1; c < M; c += 2)
				totC += costC(c, xx, yy);
			if (totR < bestR) {
				bestR = totR;
				zR = p;
			}
			if (totC < bestC) {
				bestC = totC;
				zC = p;
			}
		}
		StringBuilder res = new StringBuilder();
		if (bestR < bestC) {
			for (int r = 0; r < N; r++) {
				if (r % 2 == 0) {
					// z[0], z[1]
					int p = bestR(r, zR[0], zR[1]), q = zR[0] ^ zR[1] ^ p;
					for (int c = 0; c < M; c++)
						res.append(c % 2 == 0 ? d[p] : d[q]);
				} else {
					int p = bestR(r, zR[2], zR[3]), q = zR[2] ^ zR[3] ^ p;
					for (int c = 0; c < M; c++)
						res.append(c % 2 == 0 ? d[p] : d[q]);

				}
				res.append('\n');
			}
		} else {
			char[][] gg = new char[N][M];
			for (int c = 0; c < M; c++) {
				if (c % 2 == 0) {
					int p = bestC(c, zC[0], zC[1]), q = zC[0] ^ zC[1] ^ p;
					for (int r = 0; r < N; r++)
						gg[r][c] = r % 2 == 0 ? d[p] : d[q];
				} else {
					int p = bestC(c, zC[2], zC[3]), q = zC[2] ^ zC[3] ^ p;
					for (int r = 0; r < N; r++)
						gg[r][c] = r % 2 == 0 ? d[p] : d[q];
				}
			}
			for (char[] cc : gg)
				res.append(new String(cc) + '\n');
		}
		out.print(res);
	}

	int[] p(int a) {
		int b = 0b1111 ^ a;
		while ((a & 1 << x) == 0)
			x++;
		while ((b & 1 << xx) == 0)
			xx++;
		y = x + 1;
		yy = xx + 1;
		while ((a & 1 << y) == 0)
			y++;
		while ((b & 1 << yy) == 0)
			yy++;
		return new int[] { x, y, xx, yy };
	}

	public static void main(String[] args) {
		Scanner s = new Scanner(System.in);
		PrintWriter out = new PrintWriter(System.out);
		new NiceTable().solve(s, out);
		out.close();
		s.close();
	}

}
