You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

电王天天玩传送门。

题目描述

给出一个大小为 $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$		$1\le n,m,p,q\le 500$
$4$		无特殊限制	$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$。