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

通过次数

1

提交次数

1

Time Limit : 3 秒
Memory Limit : 52 MB

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

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

Input

第一行两个整数 n,m

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

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

Output

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

Examples

Input

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

Output

2
3
0

Hint

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