Joy of Mobile Routing

A computer science professor who loves programming has traveled to Tehran to attend our regional programming contest as a spectator. He worked hard to come, and if he finds it fun enough he plans to hold a similar contest at his own university.

As one might expect, he has become lost in our large and crowded city. Worn out, he stops at an intersection when he suddenly remembers the phone number of a friend on the organizing committee and calls him at once. The friend understands the situation and offers to guide him by phone: at each intersection he tells the professor which direction to take, and once the professor reaches the next intersection there is another call for the next direction. This continues until the professor finally sees his friend waiting at the destination intersection.

Because of poor network coverage, not every intersection has mobile reception. The professor wants to reach the contest venue as quickly as possible along a route on which he can call his friend from every intersection where he still needs directions.

The city is a grid of $R \times C$ rectangular blocks. Each block is a building 10 meters wide and 10 meters long, so the streets between the buildings meet at grid intersections. Standing at an intersection on the ground, the professor has reception when some antenna can see him: there is a straight line from his intersection to some point of the antenna that never passes through the interior of a building. The line may touch the surface of a building without losing the connection; only passing through the solid of a building blocks the signal. Each building has a given height, and each antenna is a vertical pole of a given height standing at an intersection.

Write a program that finds the length, in meters, of the shortest such route.

The first line contains a single integer $T$ ($1 \le T \le 20$), the number of independent test cases. The $T$ test cases follow.

The first line of a test case contains two integers $R$ and $C$ ($1 \le R, C \le 50$), the number of rows and columns of building blocks. Each of the next $R$ lines contains $C$ non-negative integers $H_{ij}$ ($0 \le H_{ij} \le 1000$), the building heights; the first value is the leftmost building of the topmost row. The next two lines give the starting intersection and the destination intersection, each as a row coordinate followed by a column coordinate. The topmost-leftmost intersection is $(0, 0)$ and the bottommost-rightmost intersection is $(R, C)$.

The next line contains a single integer $A$ ($0 \le A \le 100$), the number of antennas. Each of the next $A$ lines contains three integers $r$, $c$ ($0 \le r \le R$, $0 \le c \le C$) and $h$ ($0 \le h \le 1000$), meaning that an antenna of height $h$ stands at intersection $(r, c)$.

For each test case, print a single line with one integer: the shortest distance, in meters, that the professor must travel to reach the destination. If there is no valid route, print $-1$ instead.