题目描述

给出长为 $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^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$