Description

Joy 即将去度长假，因此她雇佣了技术人员为她安装一个基于红外激光束的安防系统。技术人员给了她一张图纸，将她的房子表示为一个 $R$ 行 $C$ 列的单元格网格。每个单元格包含以下之一：

• /：一面双面镜，从单元格的左下角延伸到右上角。
• \：一面双面镜，从单元格的左上角延伸到右下角。
• -：一个水平激光发射器，会向该单元格左右相邻的单元格（如果有）发射水平激光束。
• |：一个垂直激光发射器，会向该单元格上下相邻的单元格（如果有）发射垂直激光束。
• #：一面墙。（注意，房子不一定被墙包围，这也是 Joy 需要安防系统的原因之一！）
• .：空单元格，什么都没有。

激光束会沿直线传播，并穿过空单元格。当激光束遇到镜子时，会以 90 度角反射并继续传播。当向右传播的激光束遇到 / 镜子时，会反射并向上传播；而向上、向左或向下传播的激光束遇到 / 镜子时，会分别反射并向右、向下或向左传播。\ 镜子的反射方式类似：当激光束向右、上、左或下传播时遇到它，会分别反射并向下、向左、向上或向右传播。当激光束遇到墙壁或超出网格边界时，会停止传播。激光束可以与其他激光束交叉，但如果激光束击中任何激光发射器（包括可能是发射该激光束的发射器本身），该激光发射器会被摧毁！

Joy 希望确保房子里的每个空单元格都至少有一束激光通过，并且没有任何激光发射器被摧毁，否则就浪费钱了！不幸的是，技术人员已经安装好了系统，所以 Joy 现在最多只能将一些现有的激光发射器旋转 90 度，也就是说，可以将任意数量（包括 0 个）的 - 改为 |，或将 | 改为 -。

你能帮 Joy 判断是否有办法达成她的目标，或者判断是否不可能实现吗？注意，不要求最小化旋转激光发射器的数量。

Input Format

输入的第一行是测试用例数 $T$。接下来有 $T$ 组测试数据。每组数据的第一行为两个整数 $R$ 和 $C$，表示房子的网格有 $R$ 行 $C$ 列。接下来 $R$ 行，每行 $C$ 个字符，字符为 /、\、-、|、# 或 .，含义如题目描述所述。

Output Format

对于每个测试用例，输出一行，格式为 Case #x: y，其中 $x$ 是测试用例编号（从 1 开始），$y$ 为 IMPOSSIBLE（如果 Joy 无法达成目标）或 POSSIBLE（如果可以达成目标）。如果可能，请在接下来的 $R$ 行输出修改后的网格（与输入格式相同），其中可以有若干 - 被替换为 | 或反之。

如果有多种可行解，输出任意一种即可。

5
1 3
-.-
3 4
#.##
#--#
####
2 2
-.
#|
4 3
.|.
-//
.-.
#\/
3 3
/|\
\\/
./#

Case #1: IMPOSSIBLE
Case #2: POSSIBLE
#.##
#||#
####
Case #3: POSSIBLE
|.
#|
Case #4: POSSIBLE
.-.
|//
.|.
#\/
Case #5: IMPOSSIBLE

Hint

样例解释

注意，最后两个样例不会出现在 Small 数据集中。

在样例 1 中，如果一个激光发射器被设置为发射激光覆盖空单元格，则必然会摧毁另一个激光发射器。因此该情况为 IMPOSSIBLE。

在样例 2 中，最左侧的激光发射器必须旋转以覆盖空单元格。最右侧的激光发射器也必须旋转，以避免摧毁最左侧的激光发射器。

在样例 3 中，现有的激光发射器已经覆盖了所有空单元格且不会互相摧毁，因此直接输出输入网格即可。当然，给出的输出也是正确的。

在样例 4 中，一种可行解是将三个激光发射器全部旋转。不过，以下解也是可行的：

.-.
|//
.-.
#\/

因为镜子所在的单元格不需要有激光通过。（毕竟没人会偷巨大的斜面镜子，对吧？）

在样例 5 中，无论激光发射器如何旋转，都会自我摧毁，因此该情况为 IMPOSSIBLE。

数据范围

• $1 \leq T \leq 100$。
• $1 \leq C \leq 50$。
• 网格中的每个字符为 /、\、-、|、# 或 .。
• 网格中 - 和 |（即激光发射器）的总数在 $1$ 到 $100$ 之间。
• 至少有 $1$ 个 .（即空单元格）。

小数据集（测试集 1 - 可见）

• $1 \leq R \leq 5$。
• 网格中没有 / 或 \（即没有镜子）。

大数据集（测试集 2 - 隐藏）

• $1 \leq R \leq 50$。

由 ChatGPT 4.1 翻译