JOI 君居住的 IOI 市以全年炎热著称。

IOI 市是一个被划分为 $H \times W$ 个格子的长方形区域。每个格子要么是建筑物，要么是野原，要么是墙壁。建筑物共有 $P$ 个，编号从 1 到 $P$。

JOI 君只能进入建筑物或野原的格子。此外，从某个格子只能直接移动到与该格子相邻（即共享一条边）的格子，且 JOI 君在移动过程中不能离开 IOI 市。

JOI 君需要为了各种事务在不同的建筑物之间步行移动。建筑物内有空调，但野原由于阳光强烈非常炎热，每经过 1 个野原格子就需要消耗 1 单位的水。此外，由于野原没有自动售货机或饮水处，在 IOI 市移动时通常会携带水壶。容量为 $x$ 的水壶最多可以装 $x$ 单位的水。由于建筑物内有自来水，可以在建筑物内将水壶装满。

由于大水壶携带不便，JOI 君希望尽可能使用容量较小的水壶进行移动。因此，请编写一个程序，针对若干组建筑物之间的移动，求出 JOI 君完成移动所需的水壶容量的最小值。

题目描述

给定 IOI 市的地图以及 $Q$ 个询问。第 $i$ 个询问 ($1 \le i \le Q$) 为：“在建筑物 $S_i$ 和 $T_i$ 之间移动所需的水壶容量的最小值是多少？”请编写一个程序来回答这些询问。

输入格式

从标准输入读取以下数据：

• 第 1 行包含四个整数 $H, W, P, Q$，以空格分隔。这表示 IOI 市是一个 $H \times W$ 的长方形区域，市里有 $P$ 个建筑物，询问次数为 $Q$。
• 接下来的 $H$ 行描述了 IOI 市的地图。其中第 $r$ 行 ($1 \le r \le H$) 包含一个长度为 $W$ 的字符串，每个字符为 “.” 或 “#”。该字符串的第 $c$ 个字符 ($1 \le c \le W$) 表示 IOI 市从上往下第 $r$ 行、从左往右第 $c$ 列的格子类型，“.” 表示建筑物或野原，“#” 表示墙壁。
• 接下来的 $P$ 行描述了 IOI 市中建筑物的位置。其中第 $j$ 行 ($1 \le j \le P$) 包含两个整数 $A_j, B_j$，以空格分隔。这表示建筑物 $j$ 位于 IOI 市从上往下第 $A_j$ 行、从左往右第 $B_j$ 列的格子中。保证在之前给出的地图中，对应的格子为 “.”。
• 接下来的 $Q$ 行中的第 $i$ 行 ($1 \le i \le Q$) 包含两个整数 $S_i, T_i$，以空格分隔。这表示第 $i$ 个询问是关于在建筑物 $S_i$ 和 $T_i$ 之间移动所需水壶容量的最小值。

输出格式

输出 $Q$ 行。第 $i$ 行 ($1 \le i \le Q$) 输出一个整数，表示在建筑物 $S_i$ 和 $T_i$ 之间移动所需水壶容量的最小值。如果无法移动，则输出 -1。如果无需经过野原格子即可移动，则输出 0。

数据范围

所有输入数据满足以下条件：

• $1 \le H \le 2000$
• $1 \le W \le 2000$
• $2 \le P \le 200000$
• $1 \le Q \le 200000$
• $1 \le A_j \le H$ ($1 \le j \le P$)
• $1 \le B_j \le W$ ($1 \le j \le P$)
• $(A_i, B_i) \neq (A_j, B_j)$ ($1 \le i < j \le P$)
• $1 \le S_i < T_i \le P$ ($1 \le i \le Q$)

子任务

子任务 1 [10 分] 满足以下条件： $H \le 200$ $W \le 200$ * $P \le 200$

子任务 2 [30 分] 满足以下条件： $P \le 5000$ $Q = 1$

子任务 3 [30 分] 满足以下条件： $P \le 5000$ $Q \le 10000$

子任务 4 [30 分] 无额外限制。

样例

样例输入 1

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

样例输出 1

3
4
4
2

样例输入 2

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

样例输出 2

-1
7

说明

在样例 2 中，由于建筑物 1 和建筑物 2 之间有墙壁阻隔，因此无法移动。