[PA2011] Kangaroos
题目描述
给出长为 $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$ 行,每行一个整数,为询问的答案。
输入输出样例
输入样例 #1
3 3
2 5
1 3
6 6
3 5
1 10
7 9
输出样例 #1
2
3
0
说明
$1\le n\le 5\times 10^4$,$1\le m\le 2\times 10^5$,$1\le l_i\le r_i\le 10^9$,$1\le A\le B\le 10^9$