给定你所在州或省的所有房屋登记信息，你想要知道一个轴对齐正方形区域的最小尺寸，使得地址范围内的每一栋房屋都位于该区域内或其边界上。该区域划分规则较为宽松，你可以忽略范围内的任意一栋房屋以使区域更小。地址由 $1 \dots n$ 的整数给出。区域划分请求以连续的房屋范围给出。一个有效的区域是包含该范围内所有点（最多忽略一个点）的最小轴对齐正方形。

给定你所在州或省中房屋的 $(x, y)$ 位置，以及一系列区域划分请求，你必须为每个请求计算出：包含该区域划分请求中所有房屋（可能忽略其中一栋）的最小轴对齐正方形区域的边长是多少。

输入格式

每个输入包含一个测试用例。注意，你的程序可能会在不同的输入上运行多次。每个测试用例的第一行包含两个整数 $n$ 和 $q$ ($1 \le n, q \le 10^5$)，其中 $n$ 是房屋数量，$q$ 是区域划分请求的数量。

接下来的 $n$ 行，每行包含两个整数 $x$ 和 $y$ ($-10^9 \le x, y \le 10^9$)，表示你所在州或省中一栋房屋的 $(x, y)$ 坐标。房屋的地址对应于其在输入中的顺序。第一栋房屋的地址为 1，第二栋为 2，依此类推。没有两栋房屋位于同一位置。

接下来的 $q$ 行，每行包含两个整数 $a$ 和 $b$ ($1 \le a < b \le n$)，表示对地址范围在 $[a, b]$（包含边界）内的房屋进行区域划分的请求。

输出格式

输出 $q$ 行。按顺序为每个区域划分请求打印答案：在最多忽略一栋房屋的情况下，包含这些地址的房屋的所有点的最小轴对齐正方形的边长。

样例

输入 1

3 2
1 0
0 1
1000 1
1 3
2 3

输出 1

1
0

输入 2

4 2
0 0
1000 1000
300 300
1 1
1 3
2 4

输出 2

300
299