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.

走迷宫

题目描述

一个二维网格型迷宫，大小视为无限大，其中有一些障碍格点。

你初始位于 $(sx, sy)$，可以向上下左右四个方向开始移动。每次移动会沿一个方向不断前进直到遇到障碍（在走到障碍前停止），之后可以向左或向右转90度继续移动。若所要移动的方向上没有障碍或出口，则此次移动非法（视为走到无穷远处）。

每次往一个方向移动的代价为 1。当某次移动过程中经过出口，此次游戏胜利。

对于给定的迷宫，有 $k$ 个障碍，起始坐标 $(sx, sy)$，现在有 $q$ 次独立的询问，每次询问从起点到达某个出口的最小移动代价；若无解输出 -1。

输入格式

• 第一行四个正整数 $k, q, sx, sy$
• 接下来 $k$ 行，每行两个整数 $x_i, y_i$ 代表一个障碍（不保证互不相同）
• 接下来 $q$ 行，每行两个整数 $ex_i, ey_i$ 代表一个出口坐标

输出格式

• 输出 $q$ 行，每行一个整数代表最小移动代价，若无法到达则输出 -1

样例

样例1输入

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

样例1输出

5 2 3

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

数据范围

对于 100% 的数据，$k, q \leq 10^5$，坐标范围 $[-10^9, 10^9]$