5315 - 第二十四章 双指针和莫队：莫队回滚(难）
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^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