Range Closest Pair of Points Query

The closest pair of points problem is a well-known problem of computational geometry. There are $n$ points $p_1,p_2,\ldots,p_n$ in the Euclidean plane. You are given $q$ queries. The $i$-th query gives two integers $\ell_i$ and $r_i$ ($1\leq \ell_i< r_i\leq n$). For each query, find a pair of points $(u,v)$ with $\ell_i\leq u<v\leq r_i$ such that the Euclidean distance $\sqrt{(x_u-x_v)^2+(y_u-y_v)^2}$ between $p_u$ and $p_v$ is minimized.

The first line contains two integers $n$ and $q$ ($2 \leq n\leq 250\,000$, $1\leq q\leq 250\,000$), the number of points and the number of queries.

Each of the next $n$ lines contains two integers $x_i$ and $y_i$ ($1\leq x_i,y_i\leq 10^8$), the coordinates of $p_i$.

Each of the next $q$ lines contains two integers $\ell_i$ and $r_i$ ($1\leq \ell_i< r_i\leq n$), describing a query.

For each query, print one line containing the value $(x_u-x_v)^2+(y_u-y_v)^2$ for the closest pair in the range.