#4242. 水壶

内存限制:512 MiB 时间限制:50 Sec

题目描述

JOI君所居住的IOI市以一年四季都十分炎热著称。
IOI市是一个被分成纵H*横W块区域的长方形,每个区域都是建筑物、原野、墙壁之一。建筑物的区域有P个,编号为1...P。
JOI君只能进入建筑物与原野,而且每次只能走到相邻的区域中,且不能移动到市外。
JOI君因为各种各样的事情,必须在各个建筑物之间往返。虽然建筑物中的冷气设备非常好,但原野上的日光十分强烈,因此在原野上每走过一个区域都需要1单位的水。此外,原野上没有诸如自动售货机、饮水处之类的东西,因此IOI市的市民一般都携带水壶出行。大小为x的水壶最多可以装x单位的水,建筑物里有自来水可以将水壶装满。
由于携带大水壶是一件很困难的事情,因此JOI君决定携带尽量小的水壶移动。因此,为了随时能在建筑物之间移动,请你帮他写一个程序来计算最少需要多大的水壶。
现在给出IOI市的地图和Q个询问,第i个询问(1<=i<=Q)为“在建筑物Si和Ti之间移动,最小需要多大的水壶?”,请你对于每个询问输出对应的答案。

输入格式

第一行四个空格分隔的整数H,W,P,Q,表示IOI市被分成了纵H*横W块区域,有P个建筑物,Q次询问。
接下来H行,第i行(1<=i<=H)有一个长度为W的字符串,每个字符都是’.’或’#’之一,’.’表示这个位置是建筑物或原野,’#’表示这个位置是墙壁。
接下来P行描述IOI市每个建筑物的位置,第i行(1<=i<=P)有两个空格分隔的整数Ai和Bi,表示第i个建筑物的位置在第Ai行第Bi列。保证这个位置在地图中是’.’
接下来Q行,第i行(1<=i<=Q)有两个空格分隔的整数Si和Ti,表示第i个询问为“在建筑物Si和Ti之间移动,最小需要多大的水壶?”

输出格式

输出Q行,第i行(1<=i<=Q)一个整数,表示在建筑物Si和Ti之间移动最小需要多大的水壶。
如果无法到达,输出-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

数据范围与提示

1<=H<=2000

1<=W<=2000

2<=P<=2*10^5

1<=Q<=2*10^5

1<=Ai<=H(1<=i<=P)

1<=Bi<=W(1<=i<=P)

(Ai,Bi)≠(Aj,Bj)(1<=i<j<=P)

1<=Si<Ti<=P(1<=i<=Q)