题目描述

$\mathrm{JOI}$ 君所居住的 IOI 市以一年四季都十分炎热著称。

101 市被分成 $H$ 行，每行包含 $W$ 块区域。每个区域都是建筑物、原野、墙壁之一。

IOI 市有 $P$ 个区域是建筑物，坐标分别为 $\left(A_{1}, B_{1}\right),\left(A_{2}, B_{2}\right), \ldots,\left(A_{P}, B_{P}\right)$ 。

$\mathrm{JOI}$ 君只能进入建筑物与原野，而且每次只能走到相邻的区域中，且不能移动到市外。

JOI 君因为各种各样的事情，必须在各个建筑物之间往返。虽然建筑物中的冷气设备非常好，但原野上太阳非常毒辣，因此在原野上每走过一个区域都需要１升水。此外，原野上没有诸如自动售货机、饮水处之类的东西，因此 101 市的市民一般都携带水壸出行。大小为 $x$ 的水壸最多可以装 $x$ 升水，建筑物里有自来水可以将水壼装满。

由于携带大水壸是一件很困难的事情，因此 JOI 君决定携带尽量小的水壸移动。因此，为了随时能在建筑物之间移动，请你帮他写一个程序来计算最少需要多大的水壸。

现在给出 IOI 市的地图和 $Q$ 个询问，第 $i$ 个询问包含两个整数 $S_{i}, T_{i}$ ，对于每个询问，请输出：要从建筑物 $S_{i}$ 移动到 $T_{i}$ ，至少需要多大的水壸?

输入格式

第一行四个空格分隔的整数 $H, W, P, Q$ 。

接下来 $H$ 行，第 $i$ 行有一个长度为 $W$ 的字符串，每个字符都是 . 或 #之一，. 表示这个位置是建筑物或原野，＃表示这个位置是墙壁。

接下来 $P$ 行描述 101 市每个建筑物的位置，第 $i$ 行有两个空格分隔的整数 $A_{i}$ 和 $B_{i}$ ，表示第 $i$ 个建筑物的位置在第 $A_{i}$ 行第 $B_{i}$ 列。保证这个位置在地图中是 . 。

接下来 $Q$ 行，第 $i$ 行有两个空格分隔的整数 $S_{i}, T_{i 0}$

输出格式

输出 $Q$ 行，第 $i$ 行一个整数，表示要从建筑物 $S_{i}$ 移动到 $T_{i}$ ，至少需要多大的水壸。

如果无法到达，输出 -1 。如果不需要经过原野就能到达，输出 0 。

样例 #1

样例输入＃1

5 5 4 4
.....
..##.
.#...
..#..
...
11
4 2
3 3
2 5
12
24
1 3
3 4

样例输出 #1

3
4
4
2

初始状态如下:

其中、表示墙，含有数字的区域表示建筑，其他区域为原野。

如果只不经过建筑物（左图），则需要容量为 6 升的水壸；但如果经过建筑物 1 （右图），从建筑物 2 到 1 需要 3 升水，而从建筑物 1 到 4 需要 4 升水，因此只需要容量为 4 升的水䍿。

样例 #2

样例输入＃2

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

样例输出＃2

-1
7

数据范围

对于所有数据， $1 \leq H, W \leq 2000,2 \leq P \leq 2 \times 10^{5}, 1 \leq Q \leq 2 \times 10^{5}, 1 \leq A_{i} \leq H$, $1 \leq B_{i} \leq W,\left(A_{i}, B_{i}\right) \neq\left(A_{j}, B_{j}\right)(1 \leq i<j \leq P), 1 \leq S_{i}<T_{i} \leq P(1 \leq i \leq Q)$.