U584486 【五十六】六：任务
题目背景
[【五十六】历险记](https://www.luogu.com.cn/training/804406#information)
第六集：
继上一集：
通过你的帮助，56挑选了自己心仪的任务。他打开一看，那个任务的描述是这样的：
“91门派准备攻打78门派，就当91门派集结好军队准备进攻时，却发现军队中混入了78门派的卧底。他们携带了一种生化病毒，病毒每1个单位时间会向**上下左右**扩散。现在，十万火急，为了及时让军队中的仙长做好防护，你需要快速计算出每个仙长会在什么时候被感染。”
题目描述
懂的都懂，56又找到了你，希望你能帮他解决。
输入格式
第 $1$ 行：四个整数 $n , m , p , q$ ，表示军团矩阵有 $n$ 行 $m$ 列。有 $p$ 个卧底（感染源）， $q$ 为军队中仙长的数量。
接下来 $p$ 行：每行有两个整数 $x,y$ ,表示卧底在第 $x$ 行第 $y$ 列。
接下来 $q$ 行：每行有两个整数 $x,y$ ,表示仙长的位置在第 $x$ 行第 $y$ 列。
输出格式
第 $1$ 至 $q$ 行：每行一个整数，表示这个仙长感染的时间，输出顺序与输入顺序一致。
说明/提示
如下图，标记出了所有人感染的时间以及卧底和仙长的位置。
对于 $100\%$ 的数据，保证 $1≤x,y≤n,m≤10^3,1≤p,q≤10^5$
注：如果仙长就是卧底，应输出$0$