Problem Description

Xiaoming took $n$ line segments to practice playing a claw machine. He laid all the segments on the number line. For the $i$-th segment, its left endpoint is at $l_i$ and its right endpoint is at $r_i$. Xiaoming uses $m$ intervals to “frame” these segments. The range of the $i$-th interval is $[L_i, R_i]$. If at least half of a segment’s length is contained in some interval, then the segment is considered to be framed by that interval. Please compute how many segments are framed by each interval.

Input Format

The input has a total of $n + m + 1$ lines.

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

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

The next $m$ lines each contain two integers $L_i, R_i$.

Output Format

Output a total of $m$ lines, each containing one integer.

3 2
1 2
1 3
3 4
1 4
2 4

3
2

Hint

Test Case Scale and Conventions

• For $20\%$ of the testdata, $n, m \le 10^3$ is guaranteed.
• For $100\%$ of the testdata, $n, m \le 10^5$ is guaranteed, $l_i < r_i$, $0 < l_i, r_i, L_i, R_i \le 10^6$, and $\max \{r_i − l_i\} \le \min \{R_i − L_i\}$.

Problem H of Group B (C/C++), College Division, Finals of the 14th Lanqiao Cup Software Contest.

Translated by ChatGPT 5