5910：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.