← 返回题目列表

Codeforces · 1098/B

B. 漂亮的桌子

中文机器翻译题面 查看原题

给你一个 $$$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 个元素以使表格美观。