CIJEVI - Cijevi

Để 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:

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:

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 ≤ R, C ≤ 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).

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.