Description

To help design a natural gas pipeline, Croatia and Moscow are using a computer game called “Pipe Frenzy”.

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

Gas can flow through a building block in any direction. The special property of the + block is that gas must flow in two directions (one vertical and one horizontal), as shown in the following example:

A hacker deleted one building block from the plan, but the new pipeline has already been put into operation.

Write a program to determine the position of the deleted building block and its type.

Input Format

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

The next $R$ lines describe the plan. The characters are:

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

It is guaranteed that M and Z each appear exactly once.

Moscow and Croatia will each have exactly one building block. Also, the plan will have no redundant building blocks, meaning that after adding the missing block, all blocks in the plan must be used.

The input guarantees that a solution exists and is unique.

Output Format

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

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 |

Hint

Constraints

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

Notes

• This problem is worth $70$ points in total.
• Subtask 1 is hack testdata and is not scored.
• This problem is translated from COCI2008-2009 CRCI2008-2009 CIJEVI. Translator:
  https://www.luogu.com.cn/user/219791
• 2023.11.17: One set of hack testdata was added.
• 2024.02.16: Another set of hack testdata was added.

Translated by ChatGPT 5