题目描述

给定一个包含 $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$ 在指定范围内用指定方式随机生成。

测试点表格

对于每一档部分分，设其测试点编号范围为 $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$ 。

提示

本题输入输出规模较大，请使用较为快速的输入输出方式。