Gas Pipeline

Time limit1sMemory limit128 MB

Summary

Find the single missing pipe cell and its correct connector type so gas can flow from M to Z through a unique valid path using all pipe blocks.

Level: Medium6 of 10
Topics: Simulation, Graph, Implementation
Solved: No attempts yet

Problem

Zagreb and Moscow are designing a pipeline to send gas from Russia to Croatia. Before building the real pipeline, they test the design with a pipe-mania game.

The board is an R by C grid. Each cell is either empty or contains one of these seven blocks.

|: connects up and down.
-: connects left and right.
+: connects all four directions: up, right, down, and left.
1: connects right and down.
2: connects up and right.
3: connects up and left.
4: connects left and down.

Gas flows from Moscow (M) to Zagreb (Z). Gas can move in both directions through connected blocks. A + block is special: both the vertical flow and the horizontal flow must pass through it.

After the pipeline design was completed, someone removed exactly one block. The removed cell is now shown as an empty cell .. Determine the removed cell and which block used to be there.

Input

The first line contains R and C, the size of the grid. (1 <= R, C <= 25)

Each of the next R lines contains a string of length C. Every character is one of the following:

. for an empty cell
one of the block characters |, -, +, 1, 2, 3, 4
M for Moscow and Z for Zagreb

M and Z each appear exactly once. The input always has an answer, and the gas flow is unique. In the completed pipeline, M and Z are each adjacent to exactly one block. There are no unnecessary blocks: after the missing block is restored, gas flows through every block.

Output

Print the row number, the column number, and the original block character of the removed block, separated by spaces. Rows and columns are 1-indexed.

Examples3

Example 1
Input
```
3 7
.......
.M-.-Z.
.......
```
Expected output
```
2 4 -
```
Example 2
Input
```
3 5
..1-M
1-+..
Z.23.
```
Expected output
```
2 4 4
```

Example 3

Input

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

Expected output

3 3 |