Nice table

题意翻译

给定一个$nm$的矩阵，求最小的操作，使的每个$2\times2$的子矩阵中都含有`AGCT`四个字母。 每次操作可以改变矩阵中任意一个字符

题目描述

You are given an $ n \times m $ table, consisting of characters «A», «G», «C», «T». Let's call a table nice, if every $ 2 \times 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.

输入输出格式

输入格式

First line contains two positive integers $ n $ and $ m $ — number of rows and columns in the table you are given ( $ 2 \leq n, m, n \times m \leq 300\,000 $ ). Then, $ n $ lines describing the table follow. Each line contains exactly $ m $ characters «A», «G», «C», «T».

输出格式

Output $ n $ lines, $ m $ characters each. This table must be nice and differ from the input table in the minimum number of characters.

输入输出样例

输入样例 #1

2 2
AG
CT

输出样例 #1

AG
CT

输入样例 #2

3 5
AGCAG
AGCAG
AGCAG

输出样例 #2

TGCAT
CATGC
TGCAT

说明

In the first sample, the table is already nice. In the second sample, you can change 9 elements to make the table nice.