Line Segment Coverage Query

You are given n line segments on a number line. The i-th segment is represented by its endpoints li and ri.

You are also given m query intervals. The i-th query is represented by the interval \([L_i, R_i]\).

A segment is considered covered by a query interval if at least half of its length is contained in that interval. Formally, for a segment \([l, r]\) with length \(d = r - l\) and a query interval \([L, R]\), let the intersection length be:

$$ I = \max(0, \min(r, R) - \max(l, L)) $$

The segment is covered if:

$$ I \geq \frac{r - l}{2} $$

For each query interval, your task is to count how many segments are covered.

inputFormat

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

The next n lines each contain two integers li and ri, representing the endpoints of the i-th segment.

The following m lines each contain two integers Li and Ri, representing the i-th query interval.

outputFormat

Output m lines. The i-th line should contain a single integer denoting the number of segments that are covered by the i-th query interval.

sample

3 1
1 3
2 5
3 4
2 4

3