Background

This problem is not a data structure problem. It is recommended to solve F first.

Problem Description

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.

Input Format

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 Format

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

4 2
1 0
0 3
4 1
3 4
2 2
5 5

4
-1

Hint

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