escape

小 K 终于进入了宫殿大门，却发现自己身陷一个巨大的迷宫。当他凭借坚定的信念通过迷宫后，同样的迷宫再次出现，但出口的位置发生了变化。此时，他才知道自己需要通过这个迷宫 $m$ 次。

迷宫中只有小 K、障碍和出口，它们的位置均可用整数坐标表示。小 K 可以向上、下、左、右四个方向移动。每次移动时，他会沿所选方向不断前进，直到遇到障碍，并停在障碍前的最后一个整数坐标点，此后才能再次移动。如果所选方向上既没有障碍，也没有出口，则此次移动非法。

每次向一个方向移动的代价为 $1$。如果小 K 在某次移动过程中经过出口，则本次游戏胜利。

给定一个包含 $n$ 个障碍的迷宫、小 K 的起始坐标 $(X,Y)$，以及 $m$ 个不会同时存在的出口。对于每个出口，求小 K 从同一起始坐标出发到达该出口所需的最小代价。

输入格式

第一行包含两个正整数 $n$、$m$ 和两个非负整数 $X$、$Y$，分别表示障碍数量、出口数量和小 K 的起始坐标。

接下来 $n$ 行，每行包含两个非负整数 $x_{1i}$、$y_{1i}$，表示一个障碍的坐标。

随后 $m$ 行，每行包含两个非负整数 $x_{2i}$、$y_{2i}$，表示一个出口的坐标。

同行整数之间以一个空格分隔。保证起点、所有障碍和所有出口的坐标点两两不同。

输出格式

输出一行，依次给出小 K 从起始坐标到达每个出口所需的最小代价。如果某个出口无法到达，则输出 $-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

样例输出

5 2 3

数据范围

• $1\le n,m\le 10^5$；
• $0\le X,Y,x_{1i},y_{1i},x_{2i},y_{2i}\le 10^8$。

来源与许可

本题题面与测试数据整理自 BZOJ。

样例 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

输出

5 2 3