Given a sequence of $n$ points, the coordinates of the $i$-th point are $(a_i, b_i)$.
There are $q$ queries. For each query with an interval $[l, r]$, you need to calculate the value of the following expression:
$$\min_{i=l}^r \min_{j=i+1}^r (|a_i - a_j| + |b_i - b_j|)$$
It is guaranteed that the coordinates of the points in the sequence and the query intervals are randomly generated within the specified ranges using the specified method.
Input
The first line contains two positive integers $n$ and $q$.
The next $n$ lines each contain two integers $a_i$ and $b_i$, representing the coordinates $(a_i, b_i)$ of the $i$-th point.
The next $q$ lines each contain two positive integers $l$ and $r$, representing the query interval $[l, r]$.
Output
Output $q$ lines, each containing a non-negative integer representing the answer.
Examples
Input 1
4 5 1 1 2 2 1 2 2 1 1 4 1 3 1 2 2 3 3 4
Output 1
1 1 2 1 2
Example 2
See geo2.in and geo2.ans in the provided files.
The constraints for this example are consistent with test case $2$.
Example 3
See geo3.in and geo3.ans in the provided files.
The constraints for this example are consistent with test case $18$.
Implementation Details
In addition to the three examples, the provided files include rand.cpp.
rand.cpp is a data generator, which differs from the data generator used for the test cases only by the random seed.
After inputting $n, q, A, B$, the data generator can generate the entire dataset, which is output to geo.in, where $A$ and $B$ represent the upper bounds of $|a_i|$ and $|b_i|$, respectively.
Constraints
For all test cases, $2 \le n \le 10^6$, $1 \le q \le 10^6$, $|a_i|, |b_i| \le 10^9$, $1 \le l < r \le n$. It is guaranteed that $a_i, b_i, l, r$ are randomly generated within the specified ranges using the specified method.
Subtasks
| Test Case Number | $n \le$ | $q \le$ |
|---|---|---|
| $1 \sim 2$ | $2 \times 10^3$ | $2 \times 10^3$ |
| $3 \sim 8$ | $2 \times 10^4$ | $2 \times 10^4$ |
| $9 \sim 14$ | $2 \times 10^5$ | $2 \times 10^5$ |
| $15 \sim 16$ | $2 \times 10^3$ | $10^6$ |
| $17 \sim 19$ | $10^6$ | $10$ |
| $20 \sim 25$ | $10^6$ | $10^6$ |
For each group of test cases, let the range of test case numbers be $l \sim r$. Test cases $l+1 \sim r-1$ satisfy $|a_i|, |b_i| \le 10^6$, and test cases $\lfloor \frac{l+r}{2} \rfloor + 1 \sim r$ satisfy $b_i = 0$.
Note
The input and output scale for this problem is large; please use fast I/O methods.