CF1098B.Nice table

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.

给你一个 $n \times m$ 的表格，其中每个单元格包含字符 «A»、«G»、«C» 或 «T»。若该表格中每个 $2 \times 2$ 的子方阵都恰好包含全部四种不同的字符，则称其为“优美的”（nice）。你的任务是找出一个优美的表格（同样仅由 «A»、«G»、«C»、«T» 组成），使其与给定表格在尽可能少的字符位置上不同。

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

第一行包含两个正整数 $n$ 和 $m$ —— 分别表示所给表格的行数和列数（$2 \leq n, m, n \times m \leq 300\,000$）。随后是 $n$ 行，用于描述该表格。每行恰好包含 $m$ 个字符，每个字符为 «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.

输出 $n$ 行，每行 $m$ 个字符。该表格必须是“优美的”，且与输入表格在最少的字符数上不同。

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

在第一个样例中，表格已经是“优美”的。在第二个样例中，你可以修改 9 个元素使表格变得“优美”。