种小麦

题目背景

jgy、zhb、小罗翔、zy在玩我的世界,他们砍完了树，正好饥饿值也空了。所以他们想在我的世界里开一块地来种植小麦。众所周知，种田需要水。但是他们还在生存的初期，没有铁桶来装水，所以他们用了草方块来标记水放置的位置。不幸的是草方块是会蔓延的，一会以后，当他们挖完矿回来的时候，一车面包人看着一片绿色陷入了沉思，他们想知道某一块草方块是什么时候被感染的

题目描述

地面是一个 $n$ 行 $m$ 列的矩阵，每个单元是一个方块。变成草方块的方块，每过一个小时，就会向四周扩散，直到所有方块全部变成草方块。你已经掌握了需要放置的水源位置，任务是算出一块地变成草方块的时间，并且将它报告给小罗翔、zy、zhb、jgy，以便他们对挖矿、伐木、钓鱼等回来的时间进行有针对性的规划。 ps：

需要放水的位置=初始的草方块的位置

输入格式

第 $1$ 行：四个整数 $n$，$m$，$a$，$b$，表示土地矩阵有 $n$ 行 $m$ 列。有 $a$ 个需要放置水源的地方，$b$ 为土地中需要知道时间的数量。

接下来 $a$ 行：每行有两个整数 $x$，$y$，表示需要放置水源的地方在第 $x$ 行第 $y$ 列。

接下来 $b$ 行：每行有两个整数 $x$，$y$，表示需要被知道的土地在第 $x$ 行第 $y$ 列。

输出格式

第 $1$ 至 $b$ 行：每行一个整数，表示这个土地变成草方块的时间，输出顺序与输入顺序一致。如果某个需要被知道的土地的位置在需要放水的位置，那么它变成草方块的时间为 $0$。

样例 #1

样例输入 #1

10 7 1 4
4 6
10 2
1 2
6 3
3 1

样例输出 #1

10
7
5
6

提示

输入输出

由于数据原因，推荐使用 $scanf$ 输入输出 格式为

scanf("%lld%lld%lld%lld",&n,&m,&a,&b);

如上述代码中的n,m,a,b定义的是int类型，需要将lld变成d 如下：

scanf("%d%d%d%d",&n,&m,&a,&b);

$printf$ 输出例：

printf("%lld\n",map[x][y]);

占位符和输出格式与$scanf$相同，"\n"是换行符

输入输出样例 1 解释

如下图，标记出了所有土地变成草方块的时间以及需要放水的位置和需要被知道土地变成草方块的时间。（绿色为感需要放水的地方，黄色为需要被知道方块的位置） 第一行与第一列的数字为列号与行号

数据规模与约定

由于数据是电脑随机出的，我也不知道数据详细的数据范围 对于$10\%$的数据，保证$1\le n,m\le30$

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