1098B · Nice table

Problem: 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 Format: 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 Format: Output $n$ lines, $m$ characters each. This table must be nice and differ from the input table in the minimum number of characters.

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