Greatest Square

Grete has a polygon with $n$ vertices. All sides of the polygon are parallel to the coordinate axes, and each pair of adjacent sides is perpendicular. The polygon is simple, so it has no self-intersections and no self-touches.

Grete has $m$ queries. Each query gives a point $(u_i, v_i)$ strictly inside the polygon. For each point, Grete wants the side length of the largest square that lies inside the polygon and has $(u_i, v_i)$ as its lower left corner.

The input consists of several test cases and ends at end-of-file. Each test case has the following format.

The first line contains two integers $n$ and $m$, 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 the vertices in counterclockwise order.

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

For each query, print one integer on its own line: the side length of the largest square inside the polygon whose lower left corner is the query point.

• $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$.