Submit solution


Points: 0.43 (partial)
Time limit: 1.0s
Memory limit: 512M
Input: stdin
Output: stdout

Problem source:
COCI 2008/2009 - Croatian Regional
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Để giúp thiết kế một hệ thống ống dẫn dầu mới mà sẽ được dùng để vận chuyển dầu từ Nga đến Croatia, Zagreb và Moscow đang sử dụng một trò chơi có tên là Pipe Mania. Trong trò chơi này, Châu Âu được chia thành ~R~ dòng và ~C~ cột. Mỗi ô vuông có thể là ô trống hoặc chứa một trong số bảy loại ống dẫn sau:

image

Dầu chảy từ Moscow đến Zagreb. Dầu có thể chảy theo cả hai chiều theo các ống dẫn. Ống loại '+' là một loại đặc biệt mà dầu chỉ có thể chảy theo hai hướng (một là dọc, hai là ngang), như trong ví dụ sau:

image

Khi các ống dẫn dầu được đưa vào sử dụng, người ta phát hiện ra rằng các hackers xấu tính đã phá đi đúng một ống dẫn (thay nó bằng một ô trống).

Viết chương trình tìm xem ống bị phá nằm ở đâu và là loại nào.

Input

Dòng đầu chứa hai số nguyên ~R~ và ~C~, là kích thước của Châu Âu ~(1 \leq R~, ~C \leq 25)~

Tiếp theo là ~R~ dòng chứa sơ đồ mô tả hệ thống ống dẫn, mỗi dòng chứa đúng ~C~ kí tự. Các kí tự là:

  • Dấu chấm ('. '), mô tả một ô trống;
  • Các kí tự '\|' ~(ASCII~ ~124)~, '-', '+', '1', '2', '3', '4', mô tả các loại ống dẫn;
  • Các chữ cái 'M' và 'Z', thể hiện Moscow và Zagreb. Mỗi chữ chỉ xuất hiện đúng một lần trong sơ đồ.

Dòng chảy của dầu đảm bảo là duy nhất; chính xác một ống dẫn nằm kề với Moscow cũng như Zagreb. Thêm vào đó, sơ đồ không hề có ống dẫn nào thừa (tất cả các ống dẫn trong sơ đồ đều phải được sử dụng sau khi thêm vào ống dẫn bị mất).

Dữ liệu đảm bảo luôn tồn tại lời giải, và lời giải đó là duy nhất.

Output

In ra cột và dòng của ống dẫn bị phát, và loại của ống dẫn đó (một trong số bay kí tự như trong dữ liệu).

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 |

Comments

Please read the guidelines before commenting.


There are no comments at the moment.