P6349 [PA 2011] Kangaroos

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.

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 $m$ lines. Each line contains one integer, the answer to the corresponding query.

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