走迷宫

Special for beginners, ^_^

题目描述

一个二维网格型迷宫，大小视为无限大，其中有一些障碍格点 $x[i],y[i]$ 你初始位于 $(sx,sy)$ 。 ，可以向上下左右四个平行于某一个坐标轴的方向开始移动，每次移动会向一个方 向不断前进直到遇到障碍（在走到障碍处前停止移动），之后可以向左或者向右转90度、继续下一次移动。若所要移动的方向上没有障碍或出口，这次的移动就是非法的（视为走到无穷远处）。 每次往一个方向移动的代价为 1 对于给定的迷宫，有$n$个障碍 ，当某次移动过程中经过出口此次游戏胜利，可以参考样例解释。 对于给定的迷宫，有$n$个障碍，起始坐标$(sx,sy)$，现在有 $m$次独立询问，，每次询问从起点$(sx,sy)$ 到达某个出口的最小移动代价、若无解输出-1 。

Format

输入格式

第一行4个正整数 $n,m,sx,sy$ 接下来$n$行，每行2个整数$(x,y)$代表一个障碍（不保证互不相同） 接下来$$行，每行2个整数$(tx,ty)$代表一个出口坐标

Output

输出$m$行，每行一个整数代表最小移动代价

Samples

7 3 6 4
5 1
4 3
1 4
4 5
3 6
6 7
2 8
1 2
2 2
4 8

5
2
3

样例2

见下发样例

##样例解释 黑色为障碍，蓝色为起点，红圈为3个出口

数据范围

子任务1（20分）$n,m \leq 10$坐标范围$[0,10]$

子任务2（20分）$n,m \leq 1000$坐标范围 $[0,1000]$

子任务3（30分）$n,m \leq 100000$坐标范围 $[0,1000]$

子任务3（30分），$n,m \leq 100000$，坐标范围 $[0,10^{8}]$ 对于 100% 的数据，$1 \leq n,m \leq 100000$ ，坐标范围 $[0,10^{8}]$