직접 가시선

GSM 망을 구축하려면 비용과 공정이 모두 많이 든다. 기지국(BTS)을 세우고 가동한 뒤에도 망 상태를 파악하고 개선안을 세우기 위해 여러 측정을 반복해야 한다.

ACM 기술자는 전자기장 세기, 송수신 출력, 신호 품질을 재는 전용 장비를 쓴다. 이 장비는 커다란 배낭에 들어 있고, 기술자는 배낭을 메고 기지국 사이를 옮겨 다닌다. 배낭에는 측정값을 모두 저장할 메모리가 없고 몇 초 분량만 담는 작은 캐시가 있다. 그래서 측정값을 곧바로 적외선 통신(IRDA)으로 기지국에 보내야 하는데, IRDA는 기술자와 기지국 사이에 직접 가시선이 있어야 동작한다.

두 기지국을 잇는 경로 중, 언제나 둘 중 적어도 하나가 보이는 경로를 찾아라. 도시는 $P \times Q$ 크기의 정사각형 칸 격자로 나타낸다. 각 칸은 한 변이 1미터이고, 칸 $(i, j)$에는 그 자리의 지형 높이를 뜻하는 음이 아닌 정수 $Z_{i,j}$가 미터 단위로 주어진다. 즉 도시 모형은 단위 정육면체를 쌓은 것이고, 각 정육면체는 꽉 찬 상태이거나 빈 상태이다. 칸 $(i, j)$에서는 높이 0부터 $Z_{i,j}$까지의 정육면체가 꽉 차 있다.

기술자는 걸음을 단위로 움직인다. 한 걸음은 북, 남, 서, 동으로 인접한 두 칸 사이의 이동이고, 대각선으로는 갈 수 없다. 칸 $A$에서 칸 $B$로 가는 걸음은 $B$의 지형 높이가 $A$의 높이와 크게 다르지 않을 때만 허용한다. 한 걸음에 최대 1미터까지 올라갈 수 있고, 최대 3미터까지 내려갈 수 있다.

각 걸음이 끝난 지점에서는 두 기지국 중 적어도 하나가 보여야 한다. 걸음 도중에는 어느 기지국도 보이지 않는 순간이 있어도 된다. 그 구간의 자료는 캐시가 처리한다.

기지국이 보인다는 것은, 기지국 좌표의 지형 바로 위 단위 정육면체와 기술자가 서 있는 칸의 지형 바로 위 단위 정육면체 사이에 직접 가시선이 있다는 뜻이다. 두 정육면체 사이의 직접 가시선은 두 정육면체의 중심을 잇는 선분이 꽉 찬 정육면체를 하나도 관통하지 않는 것이다. 선분이 꽉 찬 정육면체에 닿기만 하는 것은 몇 개든 허용한다. 다시 말해 기지국과 기술자를 각각 자기 칸의 중앙, 지표면에서 정확히 0.5미터 위에 있는 점으로 보면 된다.

IRDA 빔은 모서리끼리 맞닿은 두 정육면체 사이로도 지나갈 수 있다. 그 둘 사이에 실제 빈틈은 없지만, 빔이 두 정육면체에 닿기만 하고 관통하지는 않기 때문이다.

기술자는 첫 번째 기지국이 있는 칸에서 출발해 두 번째 기지국이 있는 칸에 도착해야 한다.

첫 줄에 테스트 케이스의 개수를 뜻하는 양의 정수 $T$가 주어진다.

각 테스트 케이스의 첫 줄에는 두 정수 $P$와 $Q$가 공백 하나로 구분되어 주어진다 ($1 \le P, Q \le 200$). 이어서 $P$개의 줄에 각각 $Q$개의 정수가 공백으로 구분되어 주어지며, 이 값이 $Z_{i,j}$이다 ($1 \le i \le P$, $1 \le j \le Q$, $0 \le Z_{i,j} \le 5000$).

지형 정보 다음 줄, 즉 각 테스트 케이스의 마지막 줄에는 네 정수 $R_1$, $C_1$, $R_2$, $C_2$가 주어진다. 이 값은 두 기지국의 위치이고 $1 \le R_1, R_2 \le P$, $1 \le C_1, C_2 \le Q$이다. 첫 좌표는 행, 둘째 좌표는 열이다.

위 조건을 모두 만족하는 가장 짧은 경로를 구한다. 즉 모든 걸음은 인접한 두 칸 사이에서 이루어져야 하고, 지형이 너무 많이 오르거나 내려가서는 안 되며, 각 걸음이 끝난 지점에서 적어도 한 기지국이 보여야 한다.

각 테스트 케이스마다 한 줄에 The shortest path is M steps long.을 출력한다. 여기서 $M$은 필요한 걸음 수이다. 그런 경로가 없으면 Mission impossible!을 출력한다. 두 문장은 마침표와 느낌표까지 그대로 출력한다.