시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
8 초 512 MB 0 0 0 0.000%

문제

Grete has a polygon consisting of $n$ vertices. All sides of the polygon are parallel to the coordinate axes, and each two adjacent sides of the polygon are perpendicular. It is guaranteed that the polygon is simple, that is, it doesn't have self-intersections and self-touches.

Grete has $m$ queries and in each query, a point $(u_i, v_i)$ strictly inside the polygon is given. Grete would like to know the length of the side of the maximal square inside the polygon whose lower left corner is $(u_i, v_i)$.

입력

The input consists of several test cases terminated by end-of-file. For each test case:

The first line contains two integers $n$ and $m$, which are the number of vertices and the number of queries.

Each of the next $n$ lines contains two integers $x_i$ and $y_i$, the coordinates of vertices of the polygon in counterclockwise order.

Each of the next $m$ lines contains two integers $u_i$ and $v_i$, the coordinates of the lower left corner.

출력

For each query, output an integer denoting the length of the maximal square inside the polygon.

제한

  • $4 \leq n \leq 2 \times 10^5$
  • $1 \leq m \leq 2 \times 10^5$
  • $-10^8 \leq x_i, y_i, u_i, v_i \leq 10^8$
  • The sum of $n$ and the sum of $m$ do not exceed $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