시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 44 14 12 44.444%

문제

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

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

가스는 모스크바에서 자그레브로 흐른다. 가스는 빌딩 블럭을 통해 양방향으로 흐를 수 있다. '+'는 특별한 블럭으로, 두 방향 (수직, 수평)으로 흐를 수 있다. 아래 예제를 참고한다.

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

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

입력

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

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

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

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

출력

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

예제 입력

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

예제 출력

2 4 -

힌트