Description

zeromaker has conducted in-depth research on controlling his field of view for danmaku. Each danmaku appears in zeromaker’s field of view during a specific time interval, and is invisible outside that interval. In zeromaker’s opinion, the more danmaku are within the field of view, the harder the stage becomes, because this means @#￥%. Now, to evaluate the difficulty of a stage, he has already learned when each danmaku appears within his field of view. He wants to know, within a given time period, how many distinct danmaku have ever appeared in his field of view.

Note: Here, “seconds” are treated as time instants. A danmaku is considered to have appeared in the field of view if and only if the observation interval and the danmaku’s appearance interval overlap with positive length; endpoint-only contact (for example, a danmaku ends at second $2$ and the observation starts at second $2$) does not count as appearing.

Description

The first line contains two integers $n$, $m$, indicating there are $n$ danmaku in total, and zeromaker has $m$ queries.

The next $n$ lines each contain two integers $a$, $b$, meaning this danmaku appears in zeromaker’s field of view starting at second $a$ and lasts for $b$ seconds. The following $m$ lines each contain two integers $x$, $y$, meaning starting from second $x$, over $y$ seconds, ask how many danmaku have appeared at any time in that interval.

Note: Here, “seconds” are time instants. A danmaku is considered to have appeared in the field of view if and only if the observation interval and the danmaku’s appearance interval overlap with positive length; endpoint-only contact (e.g., the danmaku ends at second $2$ while the observation starts at second $2$) does not count as appearing.

Input Format

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

The next $n$ lines each contain two integers $a$, $b$, where the danmaku appears at second $a$ and lasts for $b$ seconds.

The next $m$ lines each contain two integers $x$, $y$, asking: from second $x$, over $y$ seconds, how many danmaku have ever appeared.

Output Format

Output $m$ lines, where each line is the answer to one of zeromaker’s queries.

3 2
2 5
0 10
5 8
0 6
8 2

3
2

1 2
0 10
9 1
10 1

1 
0

Hint

Sample 1 explanation:

       0  1  2  3  4  5  6  7  8  9 10 11 12 13
弹幕1        |--------------|
弹幕2  |-----------------------------|
弹幕3                 |-----------------------|
视野1  |-----------------|
视野2                          |-----|

Sample 2 explanation:

       0  1  2  3  4  5  6  7  8  9 10 11
弹幕1  |-----------------------------|
视野1                             |--|
视野2                                |--|

Constraints:

• $30\%$ of the testdata: $n, m \le 10^3$.
• $100\%$ of the testdata: $1 \le n, m \le 10^5$, $0 \le x, y, a, b \le 2^{31} - 1$.

Translated by ChatGPT 5