P8922 "MdOI R5" Squares

This problem is not a data structure problem. It is recommended to solve F first. [](https://postimg.cc/HrrHz9qD)

Given $n$ points on the plane, define a region on the plane as good if and only if it is a **square with sides parallel to the coordinate axes** and there is no given point **strictly contained** in it. Then there are $m$ queries. Each query gives a point $(x,y)$. For each query, find the side length of the largest good region that **strictly contains** $(x,y)$. If it can be infinitely large, output $-1$. A point $A$ is **strictly contained** in a region $B$ if and only if $A$ is inside $B$ and not on its boundary. To reduce tricky details, it is guaranteed that all the $n+m$ points have pairwise distinct $x$-coordinates, and pairwise distinct $y$-coordinates.

The first line contains two positive integers $n,m$. The next $n$ lines each contain two integers $x,y$, representing a given point $(x,y)$. The next $m$ lines each contain two integers $x,y$, representing the point $(x,y)$ given in a query.

Output $m$ lines. Each line contains one integer. The integer on the $i$-th line is the answer to the $i$-th query.

For $100\%$ of the data, $1\le n,m\le 3\times 10^5$, $0\le x,y\le 10^8$. $\operatorname{Subtask} 1(10\%)$: $n,m\le 10$. $\operatorname{Subtask} 2(10\%)$: $n,m\le 100$. $\operatorname{Subtask} 3(20\%)$: $n,m\le 10^3$. $\operatorname{Subtask} 4(20\%)$: $n,m\le 5\times 10^4$. $\operatorname{Subtask} 5(20\%)$: $n,m\le 10^5$. $\operatorname{Subtask} 6(20\%)$: no special constraints. #### Sample Explanation 1 For the first query, the square with bottom-left corner $(0,0)$ and side length $4$ is the largest good region that strictly contains $(2,2)$. For the second query, the square with bottom-left corner $(4,4)$ and side length $+\infty$ is the largest good region that strictly contains $(5,5)$. Translated by ChatGPT 5