该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

小田的绝密计划

题目背景

灰太狼的狼族军团卷土重来，势要攻破青青草原。羊村组织了一支先锋军前往抵抗狼族军团，但可怕的是，他们陷入了敌方的陷阱，困在了一个狭隘的峡谷里，并且，他们中有人感染了狼人病毒！如果不赶紧阻止病毒的扩散，那么他们都会变成狼人！

显然，先锋军里面出现了叛徒，而这个叛徒正是小田，小田需要在行踪暴露前，抓紧时间完成灰太狼给他的任务。

题目描述

先锋队的位置展现为一个 $n$ 行 $m$ 列的矩阵， 每个单位都是一个先锋队的成员。感染病毒的人，每过一个小时，就会向上下左右四格扩散病毒，直到所有人都感染上病毒。小田已经掌握了感染源的位置，他的任务是算出先锋队的每只羊王感染病毒的时间，并报告给灰太狼。

输入描述

第一行四个正整数 $n,m,a,b$，表示军团矩阵的行列数，以及有 $a$ 个感染源，$b$ 只羊王。

接下来 $a$ 行，每行输入两个正整数 $x,y$，表示感染源在第 $x$ 行第 $y$ 列。

接下来 $b$ 行，每行输入两个正整数 $x,y$，表示羊王的位置。

输出描述

按输入顺序在每行输出每只羊王感染病毒的时间。

注意，如果某只羊的位置在感染源，那么他感染病毒的时间为 $0$。

输入输出样例

输入 #1

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

输出 #1

3
1
3

说明/提示

【样例 1 解释】

【数据范围】

对于 $50 \%$ 的数据，有 $1 \le n,m \le 8, 1 \le a,b \le 64$ 。

对于所有测试数据，有：$1 \le n,m \le 500$，$1 \le a,b \le 10^5$ 。