题目描述

为了帮助设计天然气管道，克罗地亚和莫斯科正在使用电脑游戏「管道狂热」。

在游戏中，欧洲分为 $R$ 行和 $C$ 列。每个单元格可以为空，也可以包含七个基本管道构建块之一：

气体可以通过构建块沿任一方向流动。 构建块 + 的特殊之处在于气体必须沿两个方向（一个垂直方向，一个水平方向）流动，如以下示例所示：

当黑客从计划中删除了一个构建块时，但新管道已经开始投入使用。

编写一个程序，确定被删除构建块的位置和它的类型。

输入格式

第一行，两个整数 $R$ 和 $C$，表示欧洲的面积。

接下来，$R$ 行，表示该计划，字符有：

• .， 表示空单元格
• |，-，+，1，2，3，4，表示构件类型（见图 $1$）；
• M，表示莫斯科。
• Z，表示克罗地亚。

数据保证 M 和 Z 仅出现一次。

莫斯科和克罗地亚的每一个都将恰好有一个构建块。 此外，该计划将没有冗余构建块，即在添加丢失的块之后必须使用计划中的所有块。

输入将保证解决方案存在并且是唯一的。

输出格式

输出被擦除块的行和列，以及块的类型（输入中的 $7$ 个字符 |，-，+，1，2，3，4 之一）。

3 7
.......
.M-.-Z.
....... 

2 4 - 

3 5
..1-M
1-+..
Z.23. 

2 4 4

6 10
Z.1----4..
|.|....|..
|..14..M..
2-+++4....
..2323....
.......... 

3 3 |

提示

数据规模及约定

对于 $100\%$ 的数据，$1 \le R, C \le 25$。

说明

• 本题满分 $70$ 分。
• Subtask 1 为 hack 数据，不计分。
• 本题译自 COCI2008-2009 CRCI2008-2009 CIJEVI，译者
  https://www.luogu.com.cn/user/219791
• 2023.11.17 添加一组 hack 数据。
• 2024.02.16 再添加一组 hack 数据。