The End Dimension#12420
You're given a grid consisting of rows and columns, each cell can either be an empty cell (represented by ) , an obstacle (represented by ) or a teleportation device (represented by ).
You have to answer queries of the form:
, Find the minimum cost to reach cell starting from cell , or determine if it's impossible (it's guaranteed that neither cells are obstacles).
If you're currently on cell you can move to any of the neighboring cells that share an edge with cell as long as they don't contain an obstacle.
And if the cell has a teleportation device you can either move normally or use the device to teleport to other device on the grid.
The cost of the trip is the number of steps taken the use of the first teleportation device.
The first line consists of a single integer (1 \le t \le 250000)the number of testcases.
The description of each testcase follows.
The first line of each testcase consists of two integers and (1 \le n,m \le 500)the number of rows and the number of columns in the grid.
The next lines each contain integers a_{i,1} , a_{i,2} , ... , a_{i,m} (0 \le a_{i,j} \le 2).
The next line contains an integer (1 \le q \le 250000)the number of quereies.
The next lines each consist of integers x,y,b,c (1 \le x,b \le n , 1 \le y,c \le m).
It is guaranteed that the sum of n \cdot m over all test cases does not exceed .
It is guaranteed that the sum of over all test cases does not exceed .
For each query output the minimum cost to reach the destination, or output if it's impossible.
Example 1
Subtask ( points): No additional constraints