CIJEVI - 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.

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 |


Được gửi lên bởi:Race with time
Ngày:2009-02-17
Thời gian chạy:0.213s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO PERL6 PYPY RUST SED
Nguồn bài:COCI 2008/2009 - Croatian Regional

hide comments
2017-08-21 07:59:24 Ðặng Minh Tiến
https://kienthuc24h.com/cijevi-spoj-cijevi/
2015-06-10 17:30:19 Duc M. Pham
Code đến 252 dòng mới AC :'( Khoai quá

Bài này chủ yếu là xử lý dữ liệu chứ thuật không khó :D
2013-11-10 17:33:52 a;slkfjasl;fkj
bài này có vẻ lạ :))
2009-09-03 05:41:53 k[N]i[g]h[T]™
vậy mà mình cài toàn sai :((
2009-02-23 03:53:54 Phạm Quang Vũ
Bài nhìn thì rất khó chịu, nhưng cài rất khó sai. Các bạn nên làm thử :P
2009-02-22 04:20:06 Thiêm Nguyễn
Bai nay lam mang hang la on thoi :D Code anh tam 100 dong
2009-02-19 14:26:52 RR
Bai nay nhieu truong hop that. Minh cai ca tieng :(
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.