题目描述
给定一个包含 $n$ 个点的序列，第 $i$ 个点的坐标为 $(a_i, b_i)$ 。
共有 $q$ 次询问，每次询问一个区间 $[l, r]$ ，你需要求出下面式子的值。
$$\min_{i=l}^r \min_{j=i+1}^r (|a_i - a_j| + |b_i - b_j|)$$
保证序列中点的坐标和询问区间在指定范围内用指定方式随机生成。
输入格式
第一行输入两个正整数 $n, q$ 。
接下来 $n$ 行，每行输入两个整数 $a_i, b_i$ ，表示第 $i$ 个点的坐标为 $(a_i, b_i)$ 。
接下来 $q$ 行，每行输入两个正整数 $l, r$ ，表示询问区间 $[l, r]$ 。
输出格式
输出 $q$ 行，每行包含一个非负整数，表示答案。
样例一输入
4 5 1 1 2 2 1 2 2 1 1 4 1 3 1 2 2 3 3 4
样例一输出
1 1 2 1 2
样例二
见下发文件下的 geo2.in 与 geo2.ans 。
该样例约束与测试点 $2$ 一致。
样例三
见下发文件下的 geo3.in 与 geo3.ans 。
该样例约束与测试点 $18$ 一致。
下发文件
本题下发的文件除三个样例外还有 rand.cpp 。
rand.cpp 是一个数据生成器，与生成评测用例的数据生成器仅有随机种子不同。
输入 $n, q, A, B$ 后数据生成器才可生成整个数据，数据输出到 geo.in ，其中 $A, B$ 分别表示 $|a_i|$ 与 $|b_i|$ 的上界。
数据范围
对于所有测试点， $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$ ，保证 $a_i, b_i, l, r$ 在指定范围内用指定方式随机生成。
测试点表格
| 测试点编号 | $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$ |
对于每一档部分分，设其测试点编号范围为 $l \sim r$ ，则测试点 $l+1 \sim r-1$ 满足 $|a_i|, |b_i| \le 10^6$ ，测试点 $\lfloor \frac{l+r}{2} \rfloor + 1 \sim r$ 满足 $b_i = 0$ 。
提示
本题输入输出规模较大，请使用较为快速的输入输出方式。