Problem Description

There are $n$ points $p_1,p_2,\dots,p_n$ on a two-dimensional plane.

There are $q$ queries. In the $i$-th query, two numbers $l_i,r_i$ are given ($1\leq l_i< r_i\leq n$). You need to find a pair $(u,v)$ such that $l_i\leq u<v\leq r_i$, and the Euclidean distance $\sqrt{(x_u-x_v)^2+(y_u-y_v)^2}$ between $p_u$ and $p_v$ is minimized.

Input Format

The first line contains two integers $n,q$, representing the number of points and the number of queries.

The next $n$ lines each contain two integers $x_i,y_i$, representing the coordinates of $p_i$.

The next $q$ lines each contain two integers $l_i,r_i$ ($1\leq l_i< r_i\leq n$), representing the $i$-th query.

Output Format

For each query, output one integer per line, representing the minimum value of $(x_u-x_v)^2+(y_u-y_v)^2$.

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

2
8
8
2
2

2 1
1 1
1 1
1 2

0

Hint

Idea: Claris, Solution: Claris, Code: Claris, Data: Claris & nzhtl1477.

For $100\%$ of the testdata, $2 \leq n\leq 250\,000$, $1\leq q\leq 250\,000$, $1\leq x_i,y_i\leq 10^8$.

Translated by ChatGPT 5