Moloco 是 KAIST 市的一家广告技术公司，该城市位于一条直线坐标轴上。Moloco 拥有 $n$ 个分部，其中第 $i$ 个分部的销售领地范围为 $[\ell_i, r_i]$ 米。初始时，对于 $1 \leq i \leq n$ 满足 $\ell_i < r_i$，且对于 $1 \leq i \leq n - 1$ 满足 $r_i \leq \ell_{i + 1}$。

Moloco 定义两个分部相交，当且仅当存在一个点同时属于这两个分部的销售领地。例如，$[3, 5]$ 和 $[5, 7]$ 相交，$[1, 4]$ 和 $[2, 5]$ 相交，而 $[1, 2]$ 和 $[3, 5]$ 不相交。

Moloco 可以通过高效的广告宣传来扩大其所有分部的领地。如果 Moloco 花费 $k$ 韩元，那么每个分部都可以将自己的销售领地最多扩大 $k$ 米。扩大后的销售领地的起点和终点必须是整数值。

正式地，设第 $i$ 个分部的新销售领地为 $[\ell_i', r_i']$。则需要满足以下条件：

• $l_i' \leq l_i$ 且 $r_i \leq r_i'$。
• $(l_i - l_i') + (r_i' - r_i) \leq k$。
• $l_i'$ 和 $r_i'$ 均为整数。

由于分部过多会导致公司管理困难，Moloco 正试图将所有分部合并为一个。如果两个分部相交，则它们可以合并，合并后新分部的销售领地为这两个分部销售领地的并集。

你被 Moloco 雇佣，你对一些假设情景感到好奇：如果 Moloco 仅拥有第 $s$ 个到第 $e$ 个分部。对于每种情景，你想要求出合并 Moloco 拥有的这些分部所需的最小花费。合并发生在花费资金（可能为零）进行广告宣传并扩大所有分部之后。

给出 $q$ 次询问，每次询问中 Moloco 仅拥有第 $s$ 个到第 $e$ 个分部，求将这些分部合并为一个的最小花费。注意，当只有一个分部时，花费为 $0$。

输入格式

第一行包含两个整数 n 和 q（1 \leq n \leq 5000，1 \leq q \leq 10^6）。

接下来的 $n$ 行描述这些分部。其中的第 $i$ 行包含两个整数 \ell_i 和 r_i，表示第 $i$ 个分部的销售领地（1 \leq \ell_i < r_i \leq 10^9，r_i \leq \ell_{i + 1}）。

接下来的 $q$ 行描述询问。其中的第 $i$ 行包含两个整数 s_i 和 e_i，表示第 $i$ 次询问（1 \leq s_i \leq e_i \leq n）。

输出格式

输出 q 行。在第 i 行，输出第 i 次询问的答案：合并从第 s_i 个到第 e_i 个所有分部的最小花费。

样例

输入样例 1

5 2
1 3
5 6
10 15
20 24
28 33
1 5
3 5

输出样例 1

4
3

输入样例 2

7 7
1 3
6 10
14 18
18 19
22 24
28 29
32 40
1 7
3 5
2 6
1 2
4 4
4 7
3 4

输出样例 2

3
2
3
2
0
3
0