구간 최근접 점 쌍 질의

최근접 점 쌍 문제는 계산 기하학에서 잘 알려진 문제이다. 유클리드 평면 위에 $n$개의 점 $p_1,p_2,\ldots,p_n$이 있다. $q$개의 질의가 주어진다. $i$번째 질의에서는 두 정수 $\ell_i$와 $r_i$ ($1\leq \ell_i< r_i\leq n$)가 주어진다. 각 질의마다 $\ell_i\leq u<v\leq r_i$를 만족하는 점 쌍 $(u,v)$ 가운데, 점 $p_u$와 $p_v$ 사이의 유클리드 거리 $\sqrt{(x_u-x_v)^2+(y_u-y_v)^2}$가 최소인 쌍을 찾아야 한다.

첫 줄에 점의 개수 $n$과 질의의 개수 $q$가 주어진다 ($2 \leq n\leq 250\,000$, $1\leq q\leq 250\,000$).

다음 $n$개 줄에는 $p_i$의 좌표 $x_i$와 $y_i$가 주어진다 ($1\leq x_i,y_i\leq 10^8$).

이어서 다음 $q$개 줄에 질의 $\ell_i$와 $r_i$가 주어진다 ($1\leq \ell_i< r_i\leq n$).

각 질의마다 해당 구간에서 최근접 쌍의 값 $(x_u-x_v)^2+(y_u-y_v)^2$을 한 줄에 출력한다.