Description

A computer professor, who is fond of programming, has come to Tehran to pay a visit to our regional contest. After hearing about such an event, he has tried his best to be able to participate in the contest as a visitor. He would decide to hold such contests in his university, if he finds it fun enough.

As could be predicted, he has been lost in our large and crowded city, Tehran. He does not know where to go. Getting really tired, he is standing in a city intersection when he suddenly remembers the phone number of a friend in the organizing committee, and instantly calls him. The friend understands the situation and wants to route the professor through mobile phone calls. He plans to give the professor directions at each intersection; i.e. he tells the tired professor in which direction to move, and after reaching the next intersection, there is another phone call, to get the new direction, etc. This process continues, until the professor sees his friend at the destination intersection, waiting for him. Due to poor telecommunications installment, not all city intersections are accessible through mobile network.

The professor should get to the regional contest location as soon as possible. There are a number of antennas located in some of city intersections. A city intersection is accessible through the network if an antenna can see the point; i.e. there is an imaginary straight line connecting the intersection to any part of the antenna. The line can never cross a building, but touching a boundary does not block the mobile connection. The city is composed of R*C rectangular blocks. Each block is a building having 10 meters width and length.

You should write a program to find out the shortest possible mobile route; i.e. a route that lets the professor call his friend from each intersection, until reaching the destination. The program is given R, C and height of each building and each antenna, and the location of antennas.

Input

The only number of the first line, T, (1 <= T <= 20) is the number of different test cases to be solved. T input blocks follow, which describe different independent test cases.

The first line of a block, contains two integers R, C (1 <= R,C <= 50), the number of rows and columns of the city map, respectively. Next R lines, each contains C non-negative integers, 0 <= H_ij <= 1000, describing the building heights. The first entry is the leftmost building in the uppermost row. The coordinates of the starting and ending points are given next; the row coordinates come first in each line.

The lower and rightmost intersection is (R,C), while the opposite intersection is (0, 0).

Followed is A, (0 <= A <= 100), the number of mobile antennas. Next A lines describe the antennas by three numbers, r, c, (0 <= r <= R, 0 <= c <= C), and h, (0 <= h <= 1000). It means that there is an antenna with height h at the intersection (r, c).

Output

For each block of the input, write a single integer, which is the least distance the professor is to travel before getting to the contest, in meters. If there is no mobile route, and the professor’s friend is to choose another way for the routing, output -1 instead.

1
3 2
0 10
20 15
5 4
3 0
1 2
1
0 0 6

40

Source

Tehran 2005