A1181 | [COCI-2008_2009-regional]#1 CIJEVI

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.

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 the row and column of the erased block, and the type of the block (one of the seven characters as in the input).