水筒

题意翻译

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\leq2000$,$P,Q\leq2\times10^5$,$1\leq S_i,T_i\leq P$。 **【样例 1】** ```plain 5 5 4 4 ..... ..##. .#... ..#.. ..... 1 1 4 2 3 3 2 5 1 2 2 4 1 3 3 4 ``` 输出 ```plain 3 4 4 2 ```

题目描述

[problemUrl]: https://atcoder.jp/contests/joisc2014/tasks/joisc2014_e

输入输出格式

输入格式


输出格式


输入输出样例

暂无测试点