给你一个 $$$n \times m$$$ 表,由字符 «A», «G», «C», «T» 组成。如果每个 $$$2 \times 2$$$ 方块都包含所有四个不同的字符,我们就称这个表为好表。您的任务是找到一个漂亮的表格(也由“A”、“G”、“C”、“T”组成),其与给定表格的最小字符数不同。
输入
第一行包含两个正整数 $$$n$$$ 和 $$$m$$$ — 给定表中的行数和列数 ($$$2 \leq n, m, n \times m \leq 300\,000$$$)。然后是描述该表的 $$$n$$$ 行。每行恰好包含 $$$m$$$ 个字符《A》、《G》、《C》、《T》。
输出
输出 $$$n$$$ 行,每行 $$$m$$$ 个字符。该表必须很好,并且在最小字符数方面与输入表不同。
示例
输入 #1
2 2 AG CT
输出 #1
AG CT
输入 #2
3 5 AGCAG AGCAG AGCAG
输出 #2
TGCAT CATGC TGCAT
注意
在第一个示例中,表格已经很好了。在第二个示例中,您可以更改 9 个元素以使表格美观。