즐거운 모바일 길 안내

프로그래밍을 좋아하는 어느 컴퓨터공학과 교수가 우리 지역 프로그래밍 대회를 참관하러 테헤란에 왔다. 어렵게 시간을 내어 온 만큼, 대회가 충분히 재미있다면 자기 대학에서도 비슷한 대회를 열 생각이다.

예상대로 교수는 넓고 복잡한 도시에서 길을 잃고 말았다. 잔뜩 지친 채 한 교차로에 서 있다가, 문득 대회 조직위원회에 있는 친구의 전화번호가 떠올라 곧바로 전화를 건다. 사정을 들은 친구는 전화로 길을 안내하기로 한다. 교차로마다 어느 방향으로 가야 하는지 알려 주고, 교수가 다음 교차로에 도착하면 다시 전화를 걸어 다음 방향을 받는 식이다. 이 과정은 교수가 목적지 교차로에서 기다리는 친구를 직접 볼 때까지 계속된다.

그런데 통신 환경이 좋지 않아 모든 교차로에서 전화가 되는 것은 아니다. 교수는 아직 길 안내가 필요한 모든 교차로에서 친구에게 전화를 걸 수 있는 경로를 따라, 되도록 빨리 대회장에 도착하고 싶다.

도시는 $R \times C$ 개의 직사각형 블록으로 이루어진 격자다. 각 블록은 가로세로 10미터인 건물이며, 건물 사이의 길은 격자의 교차로에서 만난다. 교수는 땅 위의 교차로에 서 있고, 어떤 안테나가 그를 볼 수 있으면 전화가 된다. 즉, 그 교차로에서 안테나의 어떤 지점까지 이어지는 직선이 어떤 건물의 내부도 통과하지 않으면 된다. 이 직선이 건물의 표면에 닿기만 하는 것은 통신을 막지 않으며, 건물의 내부를 실제로 지나갈 때에만 신호가 차단된다. 각 건물에는 높이가 주어지고, 각 안테나는 교차로에 세워진, 주어진 높이의 수직 기둥이다.

이러한 경로 중 가장 짧은 것의 길이를 미터 단위로 구하는 프로그램을 작성하여라.

첫째 줄에 독립적인 테스트 케이스의 수 $T$ ($1 \le T \le 20$) 가 주어진다. 이어서 $T$ 개의 테스트 케이스가 주어진다.

각 테스트 케이스의 첫째 줄에는 건물 블록의 행과 열의 수를 나타내는 두 정수 $R$, $C$ ($1 \le R, C \le 50$) 가 주어진다. 이어지는 $R$ 개의 줄에는 각각 $C$ 개의 음이 아닌 정수 $H_{ij}$ ($0 \le H_{ij} \le 1000$) 가 건물의 높이로 주어지며, 첫 번째 값은 가장 위쪽 행의 가장 왼쪽 건물이다. 그다음 두 줄에는 출발 교차로와 도착 교차로가 각각 행 좌표, 열 좌표 순서로 주어진다. 가장 위 왼쪽 교차로가 $(0, 0)$ 이고, 가장 아래 오른쪽 교차로가 $(R, C)$ 이다.

그다음 줄에는 안테나의 수 $A$ ($0 \le A \le 100$) 가 주어진다. 이어지는 $A$ 개의 줄에는 각각 세 정수 $r$, $c$ ($0 \le r \le R$, $0 \le c \le C$) 와 $h$ ($0 \le h \le 1000$) 가 주어지며, 이는 교차로 $(r, c)$ 에 높이 $h$ 인 안테나가 서 있음을 뜻한다.

각 테스트 케이스마다 한 줄에 정수 하나를 출력한다. 이는 교수가 도착지에 이르기까지 이동해야 하는 최단 거리(미터)이다. 유효한 경로가 없으면 대신 $-1$ 을 출력한다.