1125. 小苏的智力开发

Dr.Su 的儿子顺利出生了,我们暂且叫他小苏。小苏的天赋异禀,他虽然现在还不会说话,但是他有一项特殊的天赋,脑洞开发。脑洞开发可以让小苏开启额外的技能和提升自己的能力。未开发的脑洞由一张二维的方格图表示,每一个脑洞每一时间单位会向周围扩散一格,开启周围的技能。

现在,Dr.Su 提前预知到了小苏的技能点的位置和小苏脑洞的起点。但是现在 Dr.Su 很忙,于是他找到了你,希望你能告诉他小苏要开启某个技能需要多少个时间单位。

输入

第一行输入两个正整数 N,M \ (1 \leq N,M≤500) 表示方格图有 NM 列。

第二行输入两个正整数 A,B \ (1≤A,B≤N \times M) 表示有 A 个脑洞起点和 B 个技能点。

接下来 A 行,每行输入两个整数 X_i,Y_i \ (1 \leq X_i≤N,1 \leq Y_i≤M) 表示脑洞的起点坐标。

接下来 B 行,每行输入两个整数 X_i,Y_i \ (1 \leq X_i≤N,1 \leq Y_i≤M) 表示技能点的坐标。

由于输入量较大,请使用较为高效的读入方式。

输出

输出一共 B 行,每行输出一个技能点对应的最快开启时间。

样例

标准输入 复制文本
5 4 
2 3
1 1
5 4
3 3
5 3
2 4
标准输出 复制文本
3
1
3

来源

2018 软件学院蓝桥杯热身赛 (For 16/17)

单点时限 4 秒
内存限制 128 MB
提交 239
通过 73