题目描述

JOI 君居住的 IOI 市，全年气温都极高，这一点是众所周知的。

IOI 市呈长方形，被划分为纵向 $H$ 行、横向 $W$ 列的网格。每个网格单元格要么是建筑物，要么是原野，要么是墙壁。其中建筑物网格共有 $P$ 个，并按 $1$ 至 $P$ 的顺序编号。

JOI 君只能进入建筑物或原野的网格单元格。此外，从某一网格单元格可直接移动的相邻网格单元格，仅限于与其共享一条边的单元格；且 JOI 君在移动过程中不可离开 IOI 市的边界。

JOI 君因各类事务，需要在不同建筑物之间步行移动。由于建筑物内有空调，而原野因阳光直射酷热难耐，因此每经过一个原野网格单元格，需消耗 $1$ 单位水。此外，原野中无自动售货机或饮水处，因此在 IOI 市内移动时通常需随身携带水桶。容量为 $x$ 的水桶最多可装 $x$ 单位水。建筑物网格单元格设有水龙头，可将水桶重新装满。

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

题目

给定 IOI 市的地图及 $Q$ 个查询。第 $i$ 个查询（$1 \le i \le Q$）要求计算“在建筑物 $S_i$ 与 $T_i$ 之间移动所需的最小水桶容量”。请编写程序，对每个查询给出答案。

输入格式

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

• 第一行包含用空格分隔的整数 $H$、$W$、$P$ 和 $Q$。这表示 IOI 市是一个由 $H \times W$ 个方格组成的矩形，IOI 市中有 $P$ 个建筑物的方格，程序将被给予 $Q$ 个问题。
• 接下来的 $H$ 行是 IOI 市的地图。其中的第 $r$ 行（$1 \leq r \leq H$）包含一个长度为 $W$ 的字符串，该字符串中的每个字符是“.”或“#”之一。该字符串的第 $c$ 个字符（$1 \leq c \leq W$）表示 IOI 市从上往下第 $r$ 行、从左往右第 $c$ 列的方格是什么，“.”表示建筑物或原野，“#”表示墙壁。
• 接下来的 $P$ 行是 IOI 市中建筑物的位置。其中的第 $j$ 行（$1 \leq j \leq P$）包含用空格分隔的整数 $A_j$ 和 $B_j$。这表示建筑物 $j$ 位于 IOI 市从上往下第 $A_j$ 行、从左往右第 $B_j$ 列的方格。在预先给出的地图上，对应的方格保证是“.”。
• 接下来的 $Q$ 行中，第 $i$ 行（$1 \leq i \leq Q$）包含用空格分隔的整数 $S_i, T_i$。这表示第 $i$ 个问题是询问“在建筑物 $S_i$ 和 $T_i$ 之间移动所需的最小水桶大小是多少”。

输出格式

在标准输出中输出 $Q$ 行。在第 $i$ 行（$1 \leq i \leq Q$）输出一个整数，表示在建筑物 $S_i$ 和 $T_i$ 之间移动所需的最小水桶大小。如果移动不可能，则输出 $-1$。如果可以在不经过草地方格的情况下进行移动，则输出 $0$。

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

3
4
4
2

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

-1
7

提示

样例 1 解释

在此输入中，IOI 市的地图如下图所示。标有黑色方块的格子表示墙壁，标有数字的格子表示对应编号的建筑物，空白格子表示草地。

:::align{center} :::

例如，考虑从建筑物 2 移动到建筑物 4。此时，如果不经过其他建筑物，最优化的路径是经过左图中用点标出的格子，这样经过的原野格子数最少，需要容量为 $6$ 的水桶。

:::align{center} :::

然而，如果像右图所示那样，在移动过程中经过建筑物 1，则从建筑物 2 到建筑物 1 的移动过程中经过 $3$ 个原野格子，从建筑物 1 到建筑物 4 的移动过程中经过 $4$ 个原野格子，因此可以使用容量为 $4$ 的水桶完成移动。此外，无法使用容量小于 $4$ 的水桶完成移动。

数据范围

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

• $1 \leq H \leq 2000$。
• $1 \leq W \leq 2000$。
• $2 \leq P \leq 200\ 000$。
• $1 \leq Q \leq 200\ 000$。
• $1 \leq A_j \leq H$（$1 \leq j \leq P$）。
• $1 \leq B_j \leq W$（$1 \leq j \leq P$）。
• $(A_i, B_i) \neq (A_j, B_j)$（$1 \leq i < j \leq P$）。
• $1 \leq S_i < T_i \leq P$（$1 \leq i \leq Q$）。

子任务

子任务 1 [10 分]

满足以下条件：

• $H \leq 200$。
• $W \leq 200$。
• $P \leq 200$。

子任务 2 [30 分]

满足以下条件：

• $P \leq 5\ 000$。
• $Q = 1$。

子任务 3 [30 分]

满足以下条件：

• $P \leq 5\ 000$。
• $Q \leq 10\ 000$。

子任务 4 [30 分]

没有额外的限制。

翻译由 Qwen3-235B 完成