电王的传送迷宫

电王天天玩传送门。

给出一个大小为 $n\times m$ 的二维网格图。 网格上的 `.` 是可以通行的路径，`#` 是不能通行的障碍。 你每次可以走到一个与当前位置四连通的且不超过边界的点。 严格来说，若你当前在点 $(x,y)$，你可以走到 $(x-1,y),(x+1,y),(x,y-1),(x,y+1)$ 中的一个，并且保证在任意时刻你的坐标 $(x,y)$ 应该满足 $1\le x\le n,1\le y\le m$。 我们从起点 $(sx,sy)$ 出发，你希望知道到达任意一个位置至少要走几步。 但这太简单了，于是精通传送门的电王在这个网格图上建造了 $p$ 个传送门，它们的坐标分别为 $(a_1,b_1),(a_2,b_2),...,(a_p,b_p)$。 而电王也设计了 $q$ 个终点，它们的坐标分别为 $(c_1,d_1),(c_2,d_2),...,(c_q,d_q)$。 假如你使用了 $i$ 次传送门，当你到达任意一个传送门，你可以选择直接传送到点 $(c_{i+1},d_{i+1})$。而第 $q$ 次传送后，所有的传送门都会失效。 **所以，传送到的位置只与你传送的次数有关，而与你到达了哪个传送门没有任何关系，我们可以认为所有传送门都是等价的。** **保证 $p$ 个传送门和 $q$ 个终点的位置都不是障碍。** 保证对于任意输入给出的坐标对应的位置上都是可以通行的路径，且这些坐标一定两两不同。 但电王有的时候并不想知道到去往任意点最少要移动几步，可能他只想知道到一个终点 $(tx,ty)$ 的最少移动步数，我们会在输入格式中了解这个测试点电王的喜好（保证 $tx,ty$ 不是一个障碍）。

第一行输入一个正整数 $opt$。 第二行两个正整数 $n,m$，表示网格图的大小。 然后的 $n$ 行，每行 $m$ 个字符，用来描述这个网格的形态。 下一行若干个正整数，前四个数分别表示 $sx,sy,p,q$，若 $opt=1$，我们还会额外输入两个数 $tx,ty$，表示电王只想知道从起点到 $(tx,ty)$ 的最少移动步数。 接下来 $p$ 行，每行两个正整数，分别表示 $a_i,b_i$ 的值。 最后 $q$ 行，每行两个正整数，分别表示 $c_i,d_i$ 的值。

若 $opt=0$，输出一个 $n\times m$ 的数组矩阵。第 $i$ 行 $j$ 列的数表示从起点 $(sx,sy)$ 到达 $(i,j)$ 最少移动几步，如果不可能到达或者这个地方是一个障碍，输出 `-1`。 否则输出一个数，表示从起点 $(sx,sy)$ 到达 $tx,ty$ 最少移动几步，如果不可能到达输出 `-1`。 **注意：使用传送门改变位置的操作，不算入移动的步数。**

0
3 4
.#..
..#.
....
3 4 1 2 
2 4
1 4
2 1

3 -1 2 1
2 3 -1 1
3 2 1 0

样例解释： 我们以从起点 $(3,4)$ 去往 $(1,1)$ 为例：首先 $(3,4)\to(2,4)$，然后使用传送门，第一次传送到 $(1,4)$。然后 $(1,4)\to (2,4)$，第二次使用传送门，到达点 $(2,1)$，最后 $(2,1)\to(1,1)$，我们使用了两次传送门，行走了 $3$ 步，所以这个路径方案的移动次数是 $3$，可以证明不存在比这更优的方案了。 **本题采用捆绑测试**。 | $\text{Subtask}$ | 分数 | $n,m,p,q$ | 特殊性质 | | :----------: | :----------: | :----------: | :----------: | | $1$ | $10$ | $p=q=0$ | 无特殊限制 | | $2$ | $20$ | $p=1$ | 无特殊限制 | | $3$ | $20$ | $1\le n,m,p,q\le 500$ | 无特殊限制 | | $4$ | $20$ | 无特殊限制 | $A$ | | $5$ | $10$ | 无特殊限制 | $B$ | | $6$ | $20$ | 无特殊限制 | 无特殊限制 | $A$：保证 $opt=1$。 $B$：保证网格中不存在不可通行的障碍 `#`。 对于所有数据，满足 $1\le n,m\le 1000,0\le p,q\le n\times m,0 \leq opt \leq 1$。