I. Range Closest Pair of Points Query
time limit per test
7 seconds
memory limit per test
1024 mebibytes
input
standard input
output
standard output

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

Input

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

In the next $$$n$$$ lines, the $$$i$$$-th line contains two integers $$$x_i$$$ and $$$y_i$$$ ($$$1\leq x_i,y_i\leq 10^8$$$), describing 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$$$), denoting a query.

Output

For each query, print a single line containing an integer, denoting the value of $$$(x_u-x_v)^2+(y_u-y_v)^2$$$.

Examples
Input
5 5
2 4
1 1
3 3
5 1
4 2
1 5
2 3
2 4
3 5
1 3
Output
2
8
8
2
2
Input
2 1
1 1
1 1
1 2
Output
0