5315 - 第二十四章 双指针和莫队:莫队回滚(难)

通过次数

1

提交次数

1

时间限制 : 3 秒
内存限制 : 52 MB

给出长为 n 的序列 a,第 i 个元素是一个区间 [l_i,r_i]

m 次询问,给出 A,B,求出 a 中最长的区间(即这个序列中的一段),使得这个区间内每个区间都与 [A,B] 有交集。输出这个最长区间的长度。

输入

第一行两个整数 n,m

接下来 n 行,第 i 行两个整数 l_i,r_i

接下来 m 行,每行两个整数 A,B,为一次询问。

输出

输出 m 行,每行一个整数,为询问的答案。

样例

输入

3 3
2 5
1 3
6 6
3 5
1 10
7 9

输出

2
3
0

提示

1\le n\le 5\times 10^41\le m\le 2\times 10^51\le l_i\le r_i\le 10^91\le A\le B\le 10^9