Advanced Traffic System

Byteland is a beautiful country with $n\times m$ cities, conveniently labeled with $1,2,3,...,n\times m$. The map of Byteland can be represented as a matrix with $n$ rows and $m$ columns, and the label of city $(i,j)$ is $id[i][j]$.

Byteasar is proud of Byteland's advanced traffic system. The traffic system of Byteland can be compressed to $e$ information. Each information contains $9$ integers $L,R,A,B,dx,C,D,dy,w$, which can be decoded using the program below:

<pre>
for(i = L;i <= R;i ++)
for(x = A;x <= B;x += dx)
for(y = C;y <= D;y += dy)
addedge(i, id[x][y], w);

</pre>

where $addedge(x, y, z)$ means adding an one-way edge with length $w$, which starts at the $x$-th city and ends at the $y$-th city.

Byteasar lives in $(sx,sy)$, he wants to know the shortest path from his position to every city, can you help him?

The first line of the input contains an integer $T(1\leq T\leq10)$, denoting the number of test cases.

In each test case, the first line of the input contains $5$ integers $n,m,e,sx,sy$ $(1\leq n,m\leq 300,0\leq e\leq 50000,1\leq sx\leq n,1\leq sy\leq m)$.

Each of the following $n$ lines contains $m$ integers, the $j$-th number of the $i$-th line denotes $id[i][j](1\leq id[i][j]\leq n\times m)$.

It is guarenteed that $id[i][j]$ forms a permutation from $1$ to $n\times m$.

Each of the following $e$ lines contains $9$ integers $L,R,A,B,dx,C,D,dy,w$, denoting each information.

$1\leq L\leq R\leq n\times m$.

$1\leq A\leq B\leq n,1\leq dx\leq n$.

$1\leq C\leq D\leq m,1\leq dy\leq m$.

$1\leq w\leq 1000$.

There are no more than $3$ test cases satisfying $e\geq 2000$.

For each test case, print a line with $n\times m$ integers, the $i$-th number denotes the shortest distance from Byteasar's position to the $i$-th city.

If the city is unreachable, please print $-1$ instead.

2
2 3 4 2 1
3 1 6
4 5 2
2 6 1 1 1 2 3 2 4
3 5 1 2 1 3 3 1 2
5 6 1 2 2 2 2 2 5
1 3 1 2 2 1 1 1 4
3 4 5 1 2
10 7 2 3
4 5 9 6
8 12 1 11
2 10 2 3 1 2 4 1 1
1 1 1 2 1 1 2 2 5
4 10 1 3 1 2 3 2 5
5 7 2 3 1 3 3 2 4
5 7 1 2 1 3 3 1 4

4 2 6 0 -1 2
1 4 -1 6 1 1 0 -1 1 6 1 1

BestCoder Round #88