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.

迷宫（$\texttt{maze}$）

【题目描述】

小 D 建造了一个的迷宫，这个迷宫可以看成一个 $n\times m$ 的网格，每个格子是空地或障碍。

小 D 有一些机器人，每个机器人可以在格子之间行走，每一步可以走到和当前格子四联通的空地上（不能出界）。

为了给这些机器人提供电量，小 D 在迷宫中建立了 $k$ 个充电站，第 $i$ 个充电站在 $(x_i,y_i)$。

每个机器人有一个电池，每走一步会消耗 $1$ 的电量，走到充电站后可以把电充满，任何时候电量不能 $<0$，特别地，从充电站出发走到相邻的某个空地不耗电。

小 D 有 $q$ 个机器人，第 $i$ 个机器人要从第 $s_j$ 个充电站走到第 $t_j$ 个充电站，他想请你对于每个机器人求出其电池容量至少是多少，如果无法做到，输出 $-1$。

【输入格式】

从 $\texttt{maze.in}$ 中读入数据。

第一行四个整数 $n,m,k,q$。

接下来 $n$ 行，每行一个长度为 $m$ 的字符串，每个字符都是 . 或 #，. 表示当前位置是空地，# 表示当前位置是障碍。

接下来 $k$ 行，每行两个整数 $x_i,y_i$ 表示第 $i$ 个充电站的位置，保证充电站都在空地上。

接下来 $q$ 行，每行两个整数 $s_j,t_j$ 表示第 $j$ 个机器人的起点和终点，保证起点和终点不相同。

【输出格式】

输出到 $\texttt{maze.out}$ 中。

输出 $q$ 行，第 $i$ 行一个整数 $w_i$ 表示机器人 $i$ 的电池容量最小是多少。

如果无论如何也不能从 $s_i$ 走到 $t_i$，输出 $-1$。

【样例 1 输入】

5 5 5 2
.....
..##.
.#...
..#..
.....
1 1
4 2
3 3
2 5
3 4
2 4
3 5

【样例 1 输出】

4
0

【样例 1 解释】

从充电站 $2$ 走到充电站 $1$ 再走到充电站 $4$，电池容量为 $4$ 就足够。

从充电站 $3$ 直接走到充电站 $5$，电池容量可以为 $0$。

【样例 2 输入】

5 5 3 2
...#.
..#..
#....
.##..
...#.
1 3
5 2
1 5
1 2
1 3

【样例 2 输出】

-1
7

【样例 3】

见下发文件中的 $\texttt{maze3.in}$ 与 $\texttt{maze3.ans}$。

该样例满足子任务 $1$ 的限制。

【样例 4】

见下发文件中的 $\texttt{maze4.in}$ 与 $\texttt{maze4.ans}$。

该样例满足子任务 $4$ 的限制。

【数据范围】

对于所有测试数据有：$1\le n,m\le 2000,2\le k\le 2\times10^5,1\le q\le 2\times 10^5$。

保证所有位置 $(x_i,y_i)$ 都是空地，保证所有 $s_j\ne t_j$。