CIJEVI - Cijevi

no tags 

To help design the new gas pipeline which will be used to deliver Russian gas to Croatia, Zagreb 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 the seven basic pipeline building blocks:

Gas flows from Moscow to Zagreb. Gas can flow in either direction through the building blocks. Block '+' is special in that gas must flow in two directions (one vertical, one horizontal), as in the following example:

Work on the new pipeline had already started when it was found that malicious hackers got hold of the plan and erased exactly one building block from the plan i.e. replaced it with an empty cell.

Write a program that determines where the block was erased from and what type it was.

Input

The first line contains two integers R and C, the dimensions of Europe (1 ≤ R, C ≤ 25)

The following R lines contain the plan, each consisting of exactly C characters. The characters are:

  • Period ('.'), representing an empty cell;
  • The characters '|' (ASCII 124), '-', '+', '1', '2', '3', '4', representing the building block types;
  • The letters 'M' and 'Z', representing Moscow and Zagreb. Each of these will appear exactly once in the plan.

The flow of gas will be uniquely determined in the input; exactly one building block will be adjacent to each of Moscow and Zagreb. Additionally, the plan will not have redundant blocks i.e. all blocks in the plan must be used after the missing block is added.

The input will be such that a solution will exist and it will be unique.

Output

Output the row and column of the erased block, and the type of the block (one of the seven characters as in the input).

Example

Input
3 7
.......
.M-.-Z.
.......
Output
2 4 -


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

Output
2 4 4


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

Output
3 3 |


hide comments
psz2007: 2021-10-09 09:22:41

AC in one go with the code in O(nm) time.
Hint : No need to go along the road.

Mind that ' Additionally, the plan will not have redundant blocks i.e. all blocks in the plan must be used after the missing block is added.'.

Last edit: 2021-10-17 02:54:28
psz2007: 2021-10-09 08:15:36

What should be the output of this input:
```
3 5
..1-M
1-.4.
Z.23.
```
Should it be 2 3 + or 2 3 3?

Edit:It should be 2 3 +.

Last edit: 2021-10-09 08:19:49

Added by:Race with time
Date:2009-02-17
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO PERL6
Resource:COCI 2008/2009 - Croatian Regional