Nice table

1000ms

262144K

Description:

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.

Input:

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:

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

Sample Input:

2 2
AG
CT

Sample Output:

AG
CT

Sample Input:

3 5
AGCAG
AGCAG
AGCAG

Sample 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.

Informação

Provedor Codeforces

Código CF1098B