Closest Pair Query

You are given n points on the 2D plane: \(p_1, p_2, \dots, p_n\). Each point \(p_i\) has coordinates \((x_i, y_i)\).

There are q queries. In the i-th query, you are given two integers \(l_i\) and \(r_i\) (with \(1 \le l_i < r_i \le n\)). Your task is to find a pair of indices \((u, v)\) satisfying \(l_i \le u < v \le r_i\) such that the Euclidean distance between \(p_u\) and \(p_v\) is minimized. The Euclidean distance between points \(p_u = (x_u, y_u)\) and \(p_v = (x_v, y_v)\) is defined as \[ \sqrt{(x_u - x_v)^2 + (y_u - y_v)^2} \]

For each query, output the minimum distance with a precision of 6 decimal places.

inputFormat

The first line contains two integers n and q separated by a space.

The next n lines each contain two integers, representing the coordinates \(x_i\) and \(y_i\) of the i-th point.

The following q lines each contain two integers \(l_i\) and \(r_i\) representing a query.

outputFormat

For each query, output one line containing the minimum Euclidean distance between any two points among \(p_{l_i}, p_{l_i+1}, \dots, p_{r_i}\). The answer should be printed with 6 decimal places.

sample

3 1
0 0
1 0
0 1
1 3

1.000000