Longest Valid Interval Subarray

You are given a sequence of n intervals, where the i-th interval is given by \([l_i, r_i]\). You are also given m queries. Each query consists of two integers, A and B. For each query, your task is to find the longest contiguous subarray (i.e. consecutive intervals in the sequence) such that every interval in that subarray intersects with the query interval \([A, B]\).

Two intervals \([l_1, r_1]\) and \([l_2, r_2]\) are said to intersect if and only if \(\max(l_1, l_2) \le \min(r_1, r_2)\). In other words, an interval \([l_i, r_i]\) intersects with \([A,B]\) if and only if:

[ \max(l_i, A) \le \min(r_i, B) \quad \Longleftrightarrow \quad l_i \le B \text{ and } r_i \ge A. ]

For each query, output the length of the longest contiguous segment of intervals satisfying the above condition. If no valid subarray exists, output 0.

inputFormat

The first line contains two integers n and m representing the number of intervals and the number of queries, respectively.

The next n lines each contain two integers \(l_i\) and \(r_i\), representing the endpoints of the i-th interval.

The following m lines each contain two integers A and B representing a query interval \([A, B]\).

outputFormat

For each query, output a single integer on a new line representing the length of the longest contiguous subarray of intervals that all intersect with the query interval \([A, B]\).

sample

3 2
1 6
2 3
4 8
2 5
3 7

3
3