Grete 有一个由 $n$ 个顶点组成的多边形。该多边形的所有边都平行于坐标轴，且每两条相邻的边都互相垂直。保证该多边形是简单多边形，即它没有自交或自触的情况。

Grete 有 $m$ 次询问，每次询问给出一个严格在多边形内部的点 $(u_i, v_i)$。Grete 想知道以 $(u_i, v_i)$ 为左下角，且完全位于多边形内部的最大正方形的边长。

输入格式

输入包含多个测试用例，以文件结束符（EOF）终止。对于每个测试用例：

第一行包含两个整数 $n$ 和 $m$，分别表示多边形的顶点数和询问次数。

接下来的 $n$ 行，每行包含两个整数 $x_i$ 和 $y_i$，表示多边形顶点的坐标，按逆时针顺序给出。

接下来的 $m$ 行，每行包含两个整数 $u_i$ 和 $v_i$，表示询问点的坐标（即正方形的左下角）。

• $4 \le n \le 2 \times 10^5$
• $1 \le m \le 2 \times 10^5$
• $-10^8 \le x_i, y_i, u_i, v_i \le 10^8$
• 所有测试用例中 $n$ 的总和与 $m$ 的总和均不超过 $2 \times 10^6$。

输出格式

对于每次询问，输出一个整数，表示多边形内部最大正方形的边长。

样例

输入 1

4 3
0 0
4 0
4 4
0 4
1 1
2 2
3 3
12 12
3050 2000
2000 2000
2000 3635
-2000 3635
-2000 2000
-2590 2000
-2590 -2000
-2000 -2000
-2000 -3481
2000 -3481
2000 -2000
3050 -2000
1415 -2882
-1100 498
-827 -3331
-114 -542
-1887 3485
-1606 -1463
-768 880
-1261 1180
330 2648
-1017 -2886
-1213 -585
-2025 -1966

输出 1

3
2
1
585
3100
2827
2542
150
3606
2755
2455
987
3017
3213
3966