题目描述

题目译自 JOISC 2014 Day2 T1「水筒」

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

IOI 市被分成 $H$ 行，每行包含 $W$ 块区域。每个区域都是建筑物、原野、墙壁之一。
IOI 市有 $P$ 个区域是建筑物，坐标分别为 $(A_1, B_1), (A_2, B_2), \ldots, (A_P, B_P)$。
JOI 君只能进入建筑物与原野，而且每次只能走到相邻的区域中，且不能移动到市外。

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

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

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

---

输入格式

第一行四个空格分隔的整数 $H, W, P, Q$。
接下来 $H$ 行，第 $i$ 行有一个长度为 $W$ 的字符串，每个字符都是 . 或 # 之一：

• . 表示这个位置是建筑物或原野；
• # 表示这个位置是墙壁。

接下来 $P$ 行描述 IOI 市每个建筑物的位置，第 $i$ 行有两个空格分隔的整数 $A_i$ 和 $B_i$，表示第 $i$ 个建筑物的位置在第 $A_i$ 行第 $B_i$ 列。保证这个位置在地图中是 .。
接下来 $Q$ 行，第 $i$ 行有两个空格分隔的整数 $S_i, T_i$。

---

输出格式

输出 $Q$ 行，第 $i$ 行一个整数，表示要从建筑物 $S_i$ 移动到 $T_i$，至少需要多大的水壶。
如果无法到达，输出 -1。如果不需要经过原野就能到达，输出 0。

---

样例 1

输入

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

输出

3
4
4
2

解释
初始状态如下：

• ■ 表示墙；
• 含有数字的区域表示建筑；
• 其他区域为原野。

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

---

样例 2

输入

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

输出

-1
7

---

数据范围与提示

对于所有数据：

• $1 \le H, W \le 2000$
• $2 \le P \le 2 \times 10^5$
• $1 \le Q \le 2 \times 10^5$
• $1 \le A_i \le H, 1 \le B_i \le W$
• $(A_i,B_i) \ne (A_j,B_j) \quad (1 \le i < j \le P)$
• $1 \le S_i < T_i \le P \quad (1 \le i \le Q)$

子任务

子任务编号	分值	附加条件
1	10	$H, W, P \le 200$
2	30	$P \le 5000, Q = 1$
3		$P \le 5000, Q \le 10^4$
4