You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

####【题目描述】 在一个 $n×m$ 的网格上地图，有 $A$ 座火山和 $B$ 个村落。某一天，所有的火山同时喷发，喷发出的岩浆开始四处扩散。若某个格子区域内有岩浆，那么 $1$ 小时后岩浆会蔓延到上下左右四个格子中。

现在，给你每座火山和每个村落的位置，请你求出每个村落会在几个小时后被岩浆淹没。若某个村落和火山在同一位置，则该时间为 $0$ 。

####【输入格式】

第一行四个整数， $n,m,A,B$ 。

接下来 $A$ 行，每行两个整数 $x,y$ ，表示第 $i$ 座火山在第 $x$ 行第 $y$ 列。

接下来 $B$ 行，每行两个整数 $x,y$ ，表示第 $i$ 个村落在第 $x$ 行第 $y$ 列。

####【输出格式】

共B行，每行一个整数，第 $i$ 行为第 $i$ 个村落被岩浆淹没的时间。

####【样例输入】

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

####【样例输出】

3
1
3

####【数据范围】

对于 $30\%$ 的数据， $1\le n,m \le 50$

对于 $60\%$ 的数据， $1\le n,m,A\le 200$

对于 $100\%$ 的数据， $1\le n,m\le 500$ ， $1\le A,B\le n × m$