Problem Description

To aid in the design of natural gas pipelines, Croatia and Moscow are using the computer game "Pipe Mania."

In the game, Europe is divided into $R$ rows and $C$ columns. Each cell can be empty or contain one of seven basic pipe components:

Gas can flow through the components in any direction. The special component + requires gas to flow in two directions (one vertical, one horizontal), as shown in the following example:

When a hacker removed a component from the plan, new pipelines have already started operating.

Write a program to determine the location and type of the removed component.

Input Format

The first line contains two integers $R$ and $C$, representing the dimensions of Europe.

The next $R$ lines represent the plan, with characters:

• ., indicating an empty cell
• |, -, +, 1, 2, 3, 4, indicating component types (see Figure 1);
• M, indicating Moscow.
• Z, indicating Croatia.

It is guaranteed that M and Z appear only once.

Both Moscow and Croatia will have exactly one component each. Additionally, the plan will have no redundant components, meaning all components in the plan must be used after adding the missing one.

The input guarantees that a solution exists and is unique.

Output Format

Output the row and column of the erased block, along with the type of the block (one of the seven characters |, -, +, 1, 2, 3, 4 from the input).

Sample Input and Output

Sample Input #1

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

Sample Output #1

2 4 -

Sample Input #2

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

Sample Output #2

2 4 4

Sample Input #3

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

Sample Output #3

3 3 |

Notes

Data Size and Constraints

For $100\%$ of the data, $1 \le R, C \le 25$.

Additional Notes

• This problem is worth $70$ points.
• Subtask 1 is for hack data and does not count towards the score.
• This problem is translated from COCI2008-2009 CRCI2008-2009 PIPES, translated by @tearing.
• Added a hack data set on November 17, 2023.
• Added another hack data set on February 16, 2024.

见题面 Input 部分

见题面 Output 部分