Bobo 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.

Bobo has m queries and in each query, a point strictly inside the polygon is given. Bobo would like to know the length of the maximal square inside the polygon whose lower left corner is .

输入描述:

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  and , the coordinates of vertices of the polygon in counterclockwise order.

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

* 
* 
* 
* The sum of n and the sum of m do not exceed .

输出描述:

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

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

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

备注: