题目描述

由于现代技术的广泛应用，自 2019 年起，全俄信息学奥林匹克开始决定在平板电脑上举行。这一新措施极大地推动了编程的普及，以至于 2020 年参加选拔阶段的选手人数空前增多。于是，2020 年决赛阶段的参赛人数也增长了，并且这一年第一次超过了 $\ldots$

在这样的复杂局面下，2020 年全俄信息学奥林匹克决赛阶段的组委会遇到了困难。为了尽可能舒适地把所有参赛者安排在大厅里，组委会决定把参赛者安排在方形桌子旁，每张桌子周围至多安排四名参赛者。事实上，对拿着平板电脑的学生来说，工作空间并不需要太大。桌子的每一边最多只能放一把椅子，否则参赛者会互相碰到胳膊。

在试机前的整整一夜，值班人员按照只有他们自己知道的原则，在桌子周围摆放椅子。看起来，他们成功地在早晨前完成了摆放任务。可是试机时发现了两个消息：一个坏消息，一个好消息。

坏消息是：如果两把椅子背靠背摆放，那么值班人员无法从它们之间通过，因此大厅中的某些空位置他们根本无法到达，这违反了奥林匹克举办规则。

好消息是：有相当大比例的报名参赛者并没有到达比赛地点，也不打算参加决赛阶段，因此可以直接搬走一部分椅子，这样规则就可以得到满足。

于是接下来一整夜，值班人员还要再次待在大厅里，这次是搬走一些多余的椅子，为自己清出通道。不过，他们可能一不小心搬走不该搬的东西，所以高级值班人员决定提前画出最终应达到的家具摆放方案。

这个方案应当只是在当前家具摆放的基础上去掉若干把椅子，不能增加家具，不能移动家具，也不能移除桌子。最终家具必须摆放成：值班人员能够到达大厅中的任意空位置，并且搬走的椅子数量尽可能少。

在本题中，空位置按照四连通理解，即只能通过公共边相邻的空格移动。判题器会检查所有空格是否都能从大厅外部连通到达。

输入格式

输入给出两个整数 $N$ 和 $M$，表示大厅宽度方向和长度方向能放下的桌子数量，并给出矩形大厅中的当前家具摆放方案。

大厅被桌子完全填满，也就是说共有 $N \times M$ 张桌子。摆放方案是一张大小为 $3N \times 3M$ 的字符表，其中每张桌子及其周围环境由一个 $3 \times 3$ 的方块表示。

在表示一张桌子和其周围椅子的 $3 \times 3$ 方块中：

• T 表示桌子；
• C 表示椅子；
• . 表示空位置。

保证桌子总是在对应 $3 \times 3$ 方块的中心位置。椅子只可能放在桌子的四条边之一旁边。

第一行包含两个整数 $N$ 和 $M$，满足：

接下来 $3N$ 行描述当前家具摆放方案，每行长度为 $3M$，只包含字符 T、C 和 .。

输出格式

输出去掉多余椅子后的大厅家具摆放方案，格式与输入中的摆放方案相同，即输出 $3N$ 行，每行长度为 $3M$。

输出方案必须满足：

1. 原来是 . 的位置仍必须是 .；
2. 原来是 T 的位置仍必须是 T；
3. 原来是 C 的位置可以保留为 C，也可以改为 .，表示搬走这把椅子；
4. 所有空位置必须从大厅外部四连通可达；
5. 被搬走的椅子数量必须尽可能少。

如果存在多种最优方案，可以输出任意一种。

样例 1

输入

2 2
......
.TCCT.
.C..C.
.C..C.
.TCCT.
......

输出

......
.T.CT.
.C..C.
.C..C.
.TCCT.
......

样例 2

输入

1 1
.C.
CTC
.C.

输出

.C.
CTC
.C.

评分方式

测试点分为三组：

每组测试点必须全部通过才能获得该组分数。