题目背景

翻译来自于 LibreOJ。

题目描述

题目译自 XXIII Olimpiada Informatyczna — III etap Żywopłot

王室园丁 Bajtazar 受命在王宫花园中打造一座树篱迷宫。花园可划分为 $m \times n$ 个方格，周围环绕着一圈围墙，北墙和南墙的正中各有一入口。在每条分隔两个方格的边上，可以种植一段树篱——使用杜松或侧柏。国王更偏爱杜松，希望迷宫中尽可能多地使用杜松树篱。然而，杜松对土壤要求较高，无法在所有边上种植。

要让树篱构成迷宫，必须满足一个额外条件：从任一入口出发，都能到达每个方格，且路径唯一（从一个方格可直接进入相邻方格，前提是分隔两者的边上没有树篱。两条路径若经过的方格集合不同，则视为不同路径）。

如上图所示，左侧展示了一个 $m=4, n=5$ 的示例花园，包含 $31$ 条边，其中 $13$ 条边可种植杜松树篱。

右侧展示了一个示例迷宫，包含 $12$ 段树篱，其中 $10$ 段为杜松，$2$ 段为侧柏。这是杜松树篱数量最多的迷宫。你的任务是编写程序，帮助 Bajtazar 设计这样的迷宫。

输入格式

第一行包含两个整数 $m, n$ $(2 \leq m, n, n$ 为奇数$)$，表示花园的尺寸。

接下来的 $m$ 行，每行包含 $n-1$ 个字符，描述垂直边（按行从左到右读取）。字符 C 表示该边可种植杜松树篱，T 表示可种植侧柏树篱。

接下来的 $m-1$ 行，每行包含 $n$ 个字符，描述水平边（同样按行从左到右读取）。

输出格式

第一行输出两个整数，分别表示构成迷宫的树篱段数和其中杜松树篱的最大数量。

接下来的 $2m-1$ 行描述迷宫的边（按输入顺序）。若某边有树篱，输出 Z；否则输出 .。

若存在多个满足国王要求的解，输出任意一个即可。

4 5
CCTT
TTCT
TCTT
TTCT
CCCTT
TCCCT
CTCTT

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

提示

样例 1 解释

输入数据描述了图左侧的花园；输出结果描述了图右侧的迷宫。

若程序仅正确输出第一行，而后续输出不正确，可获得该测试点 $52\%$ 的分数。特别地，仅输出第一行也可获得 $52\%$ 的分数。

详细子任务附加限制及分值如下表所示。