Advanced Traffic System

Byteland是一个有着$n\times m$个城市的美丽国度，这些城市编号依次为$1$到$n\times m$。Byteland的地图可以表示成一个$n$行$m$列的矩阵，其中$(i,j)$表示编号为$id[i][j]$的城市。

让Byteasar引以为豪的是Byteland发达的交通系统。Byteland的交通系统可以被压缩成$e$条信息。每条信息包含$9$个正整数$L,R,A,B,dx,C,D,dy,w$，可以解释成下面这段程序：

    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);


其中$addedge(x, y, z)$表示加一条长度为$w$的单向边，起点为第$x$个城市，终点为第$y$个城市。

Byteasar居住在$(sx,sy)$，他想知道到每个城市的最短距离，你能帮帮他吗？

第一行包含一个正整数$T(1\leq T\leq10)$，表示测试数据的组数。

每组数据的第一行包含五个整数$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)$。

接下来$n$行每行$m$个正整数，其中第$i$行第$j$个数表示$id[i][j](1\leq id[i][j]\leq n\times m)$。

数据保证所有$id[i][j]$形成了一个$1$到$n\times m$的排列。

接下来$e$行，每行$9$个正整数$L,R,A,B,dx,C,D,dy,w$，表示一条信息。

$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$。

最多只有$3$组$e\geq 2000$的数据。

对于每组数据，输出一行$n\times m$个整数，其中第$i$个数表示起点到第$i$个城市的最短距离。

若某个城市不可到达，请输出$-1$。

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