珅泽教育组织了一次校园应急演练。演练区域可以看成一个 $n$ 行 $m$ 列的网格，每个格子中有一名参与者。开始时有 $a$ 个位置已经出现传染标记；每过一个小时，所有已经带有标记的位置都会同时把标记传向上、下、左、右相邻的格子。

小婷老师记录了 $b$ 名重点观察人员的位置。请按照输入给出的顺序，计算每个人最早在第几个小时获得传染标记。如果某人的位置本来就是起始位置，那么时间为 $0$。

输入格式

第一行包含四个整数 $n,m,a,b$，分别表示网格的行数、列数、起始标记位置数和重点观察人员数。

接下来 $a$ 行，每行包含两个整数 $x,y$，表示一个起始标记位于第 $x$ 行第 $y$ 列。

再接下来 $b$ 行，每行包含两个整数 $x,y$，表示一名重点观察人员的位置。

输出格式

输出 $b$ 行，每行一个整数，依次表示每名重点观察人员最早获得标记的时间。

5 4 2 3
1 1
5 4
3 3
5 3
2 4

3
1
3

69 24 16 7
25 3
69 18
36 7
28 18
39 11
57 16
55 7
49 17
55 22
35 23
26 8
42 15
69 9
50 12
7 13
64 22
55 24
56 8
57 21
6 1
55 10
27 15
26 18

2
2
3
13
3
4
2

49 19 8 26
21 3
29 8
32 9
34 2
3 1
34 11
25 5
34 17
35 15
3 11
27 5
41 8
17 2
12 14
44 10
45 14
18 16
24 18
39 6
4 8
26 16
17 14
4 17
7 12
10 1
23 16
17 11
27 17
43 15
2 4
37 3
30 12
34 3
47 10

3
10
2
10
5
20
11
14
16
11
9
8
9
15
17
15
7
12
12
7
11
4
4
5
1
14

数据范围与约定

对于 $100\%$ 的数据，$1\le n,m\le500$，$1\le a,b\le10^5$。