Description

You are given a sequence $a$ of length $n$. The $i$-th element is an interval $[l_i, r_i]$.

There are $m$ queries. Each query gives $A, B$. Find the longest subarray (i.e., a contiguous segment of this sequence) such that every interval in this subarray intersects with $[A, B]$. Output the length of this longest subarray.

Input Format

The first line contains two integers $n, m$.

The next $n$ lines each contain two integers $l_i, r_i$.

The next $m$ lines each contain two integers $A, B$, describing one query.

Output Format

Output $m$ lines. Each line contains one integer, the answer to the corresponding query.

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

2
3
0

Hint

Constraints: $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$.

Translated by ChatGPT 5