皇家园丁 Byteasar 准备在皇家花园中种植一个树篱迷宫。Byteasar 决定将矩形花园划分为 $m \times n$ 个正方形地块。花园的周边有围墙，仅在北侧和南侧的中间各有一个入口。在每两个相邻地块之间的边上，可以种植柏树或侧柏树篱。国王偏爱柏树，但遗憾的是，柏树对土壤质量有要求，因此不能种植在所有地方。Byteasar 希望通过最大化柏树树篱段的数量来取悦国王。

如果树篱满足以下条件，则构成一个迷宫：每个地块都可以从两个入口以唯一的方式到达。（如果两个相邻地块之间没有树篱，则可以在它们之间移动。如果两条路径经过的地块集合不同，则认为它们是不同的路径。）

上图左侧展示了一个 $m = 4$ 且 $n = 5$ 的示例花园，共有 31 条共享边。其中 13 条可以种植柏树的边已被标记。

上图右侧展示了一个由 12 段树篱组成的示例迷宫，其中 10 段是柏树，2 段是侧柏。不存在柏树段更多的迷宫。你的任务是编写一个程序来帮助 Byteasar 设计这个迷宫。

输入格式

第一行包含两个整数 $m$ 和 $n$，表示花园的尺寸（$2 \le m, n$ 且 $n$ 为奇数）。接下来的 $m$ 行，每行包含 $n - 1$ 个字符，按行从左到右描述内部垂直地块边。字符 C 表示该边可以种植柏树（或侧柏），而 T 表示该边只能种植侧柏。接下来的 $m - 1$ 行，每行包含 $n$ 个字符，按行从左到右描述内部水平地块边。

输出格式

第一行应输出两个整数：构成迷宫的树篱段总数，以及其中柏树段的最大数量。随后的 $2m - 1$ 行用于描述迷宫的树篱段，格式与输入相同。如果地块边种植了树篱，则输出字符 Z，否则输出字符 .（句点）。

如果存在多种满足国王要求的方案，输出其中任意一种即可。

样例

输入格式 1

4 5
CCTT
TTCT
TCTT
TTCT
CCCTT
TCCCT
CTCTT

输出格式 1

12 10
Z..Z
..Z.
.Z.Z
..Z.
.ZZ..
.Z.Z.
Z.Z..

说明

样例说明：输入描述了图中左侧的花园；结果描述了图中右侧的迷宫。

样例测试

1ocen: $m = 4, n = 3$，柏树可以种植在任何地方； 2ocen: $m = 100, n = 99$，柏树只能种植在内部垂直地块边上； 3ocen: $m = 1000, n = 999$，柏树不能种植在任何地方。

评分标准

测试集由以下子任务组成。在每个子任务内，可能包含多个测试组。

如果你的程序输出了正确的第一行，但后续输出不正确，将获得该测试点 52% 的分数。特别地，对于任何测试点，仅输出正确的第一行即可获得 52% 的分数。