题目描述

给定一个包含 $n$ 个点的序列，第 $i$ 个点的坐标为 $(a_i,b_i)$。

共有 $q$ 次询问。每次询问给出一个区间 $[l,r]$，你需要求出区间内任意两个不同点之间的最小曼哈顿距离，即

$$\min_{i=l}^{r}\ \min_{j=i+1}^{r} \left(|a_i-a_j|+|b_i-b_j|\right).$$

保证序列中点的坐标和询问区间，均在指定范围内按照指定方式随机生成。

输入格式

第一行输入两个正整数 $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

数据范围

对于所有测试数据：

• $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\sim2$	$2\times10^3$
$3\sim8$	$2\times10^4$
$9\sim14$	$2\times10^5$
$15\sim16$	$2\times10^3$	$10^6$
$17\sim19$	$10^6$	$10$
$20\sim25$		$10^6$

对于表中的每一档部分分，设其测试点编号范围为 $L\sim R$：

• 测试点 $L+1\sim R-1$ 还满足 $|a_i|,|b_i|\le 10^6$；
• 测试点 $\left\lfloor\dfrac{L+R}{2}\right\rfloor+1\sim R$ 还满足 $b_i=0$。

提示

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