시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 1066 345 226 31.215%

문제

러시아 가스를 크로아티아로 운반하기 위해 자그레브와 모스코바는 파이프라인을 디자인하고 있다. 두 사람은 실제 디자인을 하기 전에 파이프 매니아 게임을 이용해서 설계를 해보려고 한다.

이 게임에서 유럽은 R행 C열로 나누어져 있다. 각 칸은 비어있거나, 아래 그림과 같은 일곱가지 기본 블럭으로 이루어져 있다.

가스는 모스크바에서 자그레브로 흐른다. 가스는 블럭을 통해 양방향으로 흐를 수 있다. '+'는 특별한 블럭으로, 아래 예시처럼 두 방향 (수직, 수평)으로 흘러야 한다.

파이프 라인의 설계를 마친 후 두 사람은 잠시 저녁을 먹으러 갔다. 그 사이 해커가 침임해 블럭 하나를 지웠다. 지운 블럭은 빈 칸이 되어있다.

해커가 어떤 칸을 지웠고, 그 칸에는 원래 어떤 블럭이 있었는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 유럽의 크기 R과 C가 주어진다. (1 ≤ R, C ≤ 25)

다음 R개 줄에는 C개 글자가 주어지며, 다음과 같은 글자로 이루어져 있다.

  • 빈칸을 나타내는 '.'
  • 블럭을 나타내는 '|'(아스키 124), '-','+','1','2','3','4'
  • 모스크바의 위치를 나타내는 'M'과 자그레브를 나타내는 'Z'. 두 글자는 한 번만 주어진다.

항상 답이 존재하고, 가스의 흐름이 유일한 경우만 입력으로 주어진다, 또, 모스크바와 자그레브가 하나의 블럭과 인접해 있는 입력만 주어진다. 또, 불필요한 블럭이 존재하지 않는다. 즉, 없어진 블럭을 추가하면, 모든 블럭에 가스가 흐르게 된다.

출력

지워진 블럭의 행과 열 위치를 출력하고, 어떤 블럭이었는지를 출력한다.

예제 입력 1

3 7
.......
.M-.-Z.
.......

예제 출력 1

2 4 -

예제 입력 2

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

예제 출력 2

2 4 4

예제 입력 3

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

예제 출력 3

3 3 |
W3sicHJvYmxlbV9pZCI6IjI5MzEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFjMDBcdWMyYTRcdWFkMDAiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YjdlY1x1YzJkY1x1YzU0NCBcdWFjMDBcdWMyYTRcdWI5N2MgXHVkMDZjXHViODVjXHVjNTQ0XHVkMmYwXHVjNTQ0XHViODVjIFx1YzZiNFx1YmMxOFx1ZDU1OFx1YWUzMCBcdWM3MDRcdWQ1NzQgXHVjNzkwXHVhZGY4XHViODA4XHViZTBjXHVjNjQwIFx1YmFhOFx1YzJhNFx1Y2Y1NFx1YmMxNFx1YjI5NCBcdWQzMGNcdWM3NzRcdWQ1MDRcdWI3N2NcdWM3NzhcdWM3NDQgXHViNTE0XHVjNzkwXHVjNzc4XHVkNTU4XHVhY2UwIFx1Yzc4OFx1YjJlNC4gXHViNDUwIFx1YzBhY1x1Yjc4Y1x1Yzc0MCBcdWMyZTRcdWM4MWMgXHViNTE0XHVjNzkwXHVjNzc4XHVjNzQ0IFx1ZDU1OFx1YWUzMCBcdWM4MDRcdWM1ZDAgXHVkMzBjXHVjNzc0XHVkNTA0IFx1YjllNFx1YjJjOFx1YzU0NCBcdWFjOGNcdWM3ODRcdWM3NDQgXHVjNzc0XHVjNmE5XHVkNTc0XHVjMTFjIFx1YzEyNFx1YWNjNFx1Yjk3YyBcdWQ1NzRcdWJjZjRcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3NzQgXHVhYzhjXHVjNzg0XHVjNWQwXHVjMTFjIFx1YzcyMFx1YjdmZFx1Yzc0MCBSXHVkNTg5IENcdWM1ZjRcdWI4NWMgXHViMDk4XHViMjA0XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHVhYzAxIFx1Y2U3OFx1Yzc0MCBcdWJlNDRcdWM1YjRcdWM3ODhcdWFjNzBcdWIwOTgsIFx1YzU0NFx1Yjc5OCBcdWFkZjhcdWI5YmNcdWFjZmMgXHVhYzE5XHVjNzQwIFx1Yzc3Y1x1YWNmMVx1YWMwMFx1YzljMCBcdWFlMzBcdWJjZjggXHViZTE0XHViN2VkXHVjNzNjXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvcGlwZTEucG5nXCIgc3R5bGU9XCJoZWlnaHQ6OTJweDsgd2lkdGg6NTg1cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+XHVhYzAwXHVjMmE0XHViMjk0IFx1YmFhOFx1YzJhNFx1ZDA2Y1x1YmMxNFx1YzVkMFx1YzExYyBcdWM3OTBcdWFkZjhcdWI4MDhcdWJlMGNcdWI4NWMgXHVkNzUwXHViOTc4XHViMmU0LiBcdWFjMDBcdWMyYTRcdWIyOTQgXHViZTE0XHViN2VkXHVjNzQ0IFx1ZDFiNVx1ZDU3NCBcdWM1OTFcdWJjMjlcdWQ1YTVcdWM3M2NcdWI4NWMgXHVkNzUwXHViOTdjIFx1YzIxOCBcdWM3ODhcdWIyZTQuICYjMzk7KyYjMzk7XHViMjk0IFx1ZDJiOVx1YmNjNFx1ZDU1YyBcdWJlMTRcdWI3ZWRcdWM3M2NcdWI4NWMsIFx1YzU0NFx1Yjc5OCBcdWM2MDhcdWMyZGNcdWNjOThcdWI3ZmMgXHViNDUwIFx1YmMyOVx1ZDVhNSAoXHVjMjE4XHVjOWMxLCBcdWMyMThcdWQzYzkpXHVjNzNjXHViODVjIFx1ZDc1OFx1YjdlY1x1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvcGlwZTIoMSkucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MTc1cHg7IHdpZHRoOjI3MHB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPlx1ZDMwY1x1Yzc3NFx1ZDUwNCBcdWI3N2NcdWM3NzhcdWM3NTggXHVjMTI0XHVhY2M0XHViOTdjIFx1YjljOFx1Y2U1YyBcdWQ2YzQgXHViNDUwIFx1YzBhY1x1Yjc4Y1x1Yzc0MCBcdWM3YTBcdWMyZGMgXHVjODAwXHViMTQxXHVjNzQ0IFx1YmEzOVx1YzczY1x1YjdlYyBcdWFjMTRcdWIyZTQuIFx1YWRmOCBcdWMwYWNcdWM3NzQgXHVkNTc0XHVjZWU0XHVhYzAwIFx1Y2U2OFx1Yzc4NFx1ZDU3NCBcdWJlMTRcdWI3ZWQgXHVkNTU4XHViMDk4XHViOTdjIFx1YzljMFx1YzZlMFx1YjJlNC4gXHVjOWMwXHVjNmI0IFx1YmUxNFx1YjdlZFx1Yzc0MCBcdWJlNDggXHVjZTc4XHVjNzc0IFx1YjQxOFx1YzViNFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkNTc0XHVjZWU0XHVhYzAwIFx1YzViNFx1YjVhNCBcdWNlNzhcdWM3NDQgXHVjOWMwXHVjNmUwXHVhY2UwLCBcdWFkZjggXHVjZTc4XHVjNWQwXHViMjk0IFx1YzZkMFx1Yjc5OCBcdWM1YjRcdWI1YTQgXHViZTE0XHViN2VkXHVjNzc0IFx1Yzc4OFx1YzVjOFx1YjI5NFx1YzljMCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjNzIwXHViN2ZkXHVjNzU4IFx1ZDA2Y1x1YWUzMCBSXHVhY2ZjIENcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IFIsIEMgJmxlOyAyNSk8XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjIFJcdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IENcdWFjMWMgXHVhZTAwXHVjNzkwXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljMFx1YmE3MCwgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc0MCBcdWFlMDBcdWM3OTBcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5cdWJlNDhcdWNlNzhcdWM3NDQgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0ICYjMzk7LiYjMzk7PFwvbGk+XHJcblx0PGxpPlx1YmUxNFx1YjdlZFx1Yzc0NCBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgJiMzOTt8JiMzOTsoXHVjNTQ0XHVjMmE0XHVkMGE0IDEyNCksICYjMzk7LSYjMzk7LCYjMzk7KyYjMzk7LCYjMzk7MSYjMzk7LCYjMzk7MiYjMzk7LCYjMzk7MyYjMzk7LCYjMzk7NCYjMzk7PFwvbGk+XHJcblx0PGxpPlx1YmFhOFx1YzJhNFx1ZDA2Y1x1YmMxNFx1Yzc1OCBcdWM3MDRcdWNlNThcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0ICYjMzk7TSYjMzk7XHVhY2ZjIFx1Yzc5MFx1YWRmOFx1YjgwOFx1YmUwY1x1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgJiMzOTtaJiMzOTsuIFx1YjQ1MCBcdWFlMDBcdWM3OTBcdWIyOTQgXHVkNTVjIFx1YmM4OFx1YjljYyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+XHVkNTZkXHVjMGMxIFx1YjJmNVx1Yzc3NCBcdWM4NzRcdWM3YWNcdWQ1NThcdWFjZTAsIFx1YWMwMFx1YzJhNFx1Yzc1OCBcdWQ3NTBcdWI5ODRcdWM3NzQgXHVjNzIwXHVjNzdjXHVkNTVjIFx1YWNiZFx1YzZiMFx1YjljYyBcdWM3ODVcdWI4MjVcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LCBcdWI2MTAsIFx1YmFhOFx1YzJhNFx1ZDA2Y1x1YmMxNFx1YzY0MCZuYnNwO1x1Yzc5MFx1YWRmOFx1YjgwOFx1YmUwY1x1YWMwMCBcdWQ1NThcdWIwOThcdWM3NTggXHViZTE0XHViN2VkXHVhY2ZjIFx1Yzc3OFx1YzgxMVx1ZDU3NCBcdWM3ODhcdWIyOTQgXHVjNzg1XHViODI1XHViOWNjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4mbmJzcDtcdWI2MTAsIFx1YmQ4OFx1ZDU0NFx1YzY5NFx1ZDU1YyBcdWJlMTRcdWI3ZWRcdWM3NzQgXHVjODc0XHVjN2FjXHVkNTU4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC4gXHVjOTg5LCBcdWM1YzZcdWM1YjRcdWM5YzQgXHViZTE0XHViN2VkXHVjNzQ0IFx1Y2Q5NFx1YWMwMFx1ZDU1OFx1YmE3NCwgXHViYWE4XHViNGUwIFx1YmUxNFx1YjdlZFx1YzVkMCBcdWFjMDBcdWMyYTRcdWFjMDAgXHVkNzUwXHViOTc0XHVhYzhjIFx1YjQxY1x1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWM5YzBcdWM2Y2NcdWM5YzQgXHViZTE0XHViN2VkXHVjNzU4IFx1ZDU4OVx1YWNmYyBcdWM1ZjQgXHVjNzA0XHVjZTU4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YWNlMCwgXHVjNWI0XHViNWE0IFx1YmUxNFx1YjdlZFx1Yzc3NFx1YzVjOFx1YjI5NFx1YzljMFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMjkzMSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkNJSkVWSSIsImRlc2NyaXB0aW9uIjoiPHA+VG8gaGVscCBkZXNpZ24gdGhlIG5ldyBnYXMgcGlwZWxpbmUgd2hpY2ggd2lsbCBiZSB1c2VkIHRvIGRlbGl2ZXIgUnVzc2lhbiBnYXMgdG8gQ3JvYXRpYSwgWmFncmViIGFuZCBNb3Njb3cgYXJlIHVzaW5nIHRoZSBjb21wdXRlciBnYW1lIFBpcGUgTWFuaWEuIEluIHRoZSBnYW1lLCBFdXJvcGUgaXMgZGl2aWRlZCBpbnRvIFIgcm93cyBhbmQgQyBjb2x1bW5zLiBFYWNoIGNlbGwgY2FuIGJlIGVtcHR5IG9yIGNvbnRhaW4gb25lIG9mIHRoZSBzZXZlbiBiYXNpYyBwaXBlbGluZSBidWlsZGluZyBibG9ja3M6PFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvcGlwZTEucG5nXCIgc3R5bGU9XCJoZWlnaHQ6OTJweDsgd2lkdGg6NTg1cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+R2FzIGZsb3dzIGZyb20gTW9zY293IHRvIFphZ3JlYi4gR2FzIGNhbiBmbG93IGluIGVpdGhlciBkaXJlY3Rpb24gdGhyb3VnaCB0aGUgYnVpbGRpbmcgYmxvY2tzLiBCbG9jayAmIzM5OysmIzM5OyBpcyBzcGVjaWFsIGluIHRoYXQgZ2FzIG11c3QgZmxvdyBpbiB0d28gZGlyZWN0aW9ucyAob25lIHZlcnRpY2FsLCBvbmUgaG9yaXpvbnRhbCksIGFzIGluIHRoZSBmb2xsb3dpbmcgZXhhbXBsZTo8XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9waXBlMigxKS5wbmdcIiBzdHlsZT1cImhlaWdodDoxNzVweDsgd2lkdGg6MjcwcHhcIiBcLz48XC9wPlxyXG5cclxuPHA+V29yayBvbiB0aGUgbmV3IHBpcGVsaW5lIGhhZCBhbHJlYWR5IHN0YXJ0ZWQgd2hlbiBpdCB3YXMgZm91bmQgdGhhdCBtYWxpY2lvdXMgaGFja2VycyBnb3QgaG9sZCBvZiB0aGUgcGxhbiBhbmQgZXJhc2VkIGV4YWN0bHkgb25lIGJ1aWxkaW5nIGJsb2NrIGZyb20gdGhlIHBsYW4gaS5lLiByZXBsYWNlZCBpdCB3aXRoIGFuIGVtcHR5IGNlbGwuJm5ic3A7PFwvcD5cclxuXHJcbjxwPldyaXRlIGEgcHJvZ3JhbSB0aGF0IGRldGVybWluZXMgd2hlcmUgdGhlIGJsb2NrIHdhcyBlcmFzZWQgZnJvbSBhbmQgd2hhdCB0eXBlIGl0IHdhcy4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIGNvbnRhaW5zIHR3byBpbnRlZ2VycyBSIGFuZCBDLCB0aGUgZGltZW5zaW9ucyBvZiBFdXJvcGUgKDEgJmxlOyBSLCBDICZsZTsgMjUpLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgZm9sbG93aW5nIFIgbGluZXMgY29udGFpbiB0aGUgcGxhbiwgZWFjaCBjb25zaXN0aW5nIG9mIGV4YWN0bHkgQyBjaGFyYWN0ZXJzLiBUaGUgY2hhcmFjdGVycyBhcmU6Jm5ic3A7PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+UGVyaW9kICgmIzM5Oy4mIzM5OyksIHJlcHJlc2VudGluZyBhbiBlbXB0eSBjZWxsOyZuYnNwOzxcL2xpPlxyXG5cdDxsaT5UaGUgY2hhcmFjdGVycyAmIzM5O3wmIzM5OyAoQVNDSUkgMTI0KSwgJiMzOTstJiMzOTssICYjMzk7KyYjMzk7LCAmIzM5OzEmIzM5OywgJiMzOTsyJiMzOTssICYjMzk7MyYjMzk7LCAmIzM5OzQmIzM5OywgcmVwcmVzZW50aW5nIHRoZSBidWlsZGluZyBibG9jayB0eXBlczsmbmJzcDs8XC9saT5cclxuXHQ8bGk+VGhlIGxldHRlcnMgJiMzOTtNJiMzOTsgYW5kICYjMzk7WiYjMzk7LCByZXByZXNlbnRpbmcgTW9zY293IGFuZCBaYWdyZWIuIEVhY2ggb2YgdGhlc2Ugd2lsbCBhcHBlYXIgZXhhY3RseSBvbmNlIGluIHRoZSBwbGFuLiZuYnNwOzxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlRoZSBmbG93IG9mIGdhcyB3aWxsIGJlIHVuaXF1ZWx5IGRldGVybWluZWQgaW4gdGhlIGlucHV0OyBleGFjdGx5IG9uZSBidWlsZGluZyBibG9jayB3aWxsIGJlIGFkamFjZW50IHRvIGVhY2ggb2YgTW9zY293IGFuZCBaYWdyZWIuIEFkZGl0aW9uYWxseSwgdGhlIHBsYW4gd2lsbCBub3QgaGF2ZSByZWR1bmRhbnQgYmxvY2tzIGkuZS4gYWxsIGJsb2NrcyBpbiB0aGUgcGxhbiBtdXN0IGJlIHVzZWQgYWZ0ZXIgdGhlIG1pc3NpbmcgYmxvY2sgaXMgYWRkZWQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSBpbnB1dCB3aWxsIGJlIHN1Y2ggdGhhdCBhIHNvbHV0aW9uIHdpbGwgZXhpc3QgYW5kIGl0IHdpbGwgYmUgdW5pcXVlLiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPk91dHB1dCB0aGUgcm93IGFuZCBjb2x1bW4gb2YgdGhlIGVyYXNlZCBibG9jaywgYW5kIHRoZSB0eXBlIG9mIHRoZSBibG9jayAob25lIG9mIHRoZSBzZXZlbiBjaGFyYWN0ZXJzIGFzIGluIHRoZSBpbnB1dCkuJm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d