QOJ.ac

QOJ

Time Limit: 2 s Memory Limit: 512 MB Total points: 100

# 8672. 排队

统计

P大的澡堂需要排队,每个人有一个偏好$l_i,r_i$。

如果第 $i$ 个人去洗澡时,发现有 $> r_i$ 个人排队,他会直接离开(因为排队的人实在太多),如果有 $[0, l_i)$ 个人排队,他也会离开(因为人太少了,排队时不能聊天,比较没意思,还不如去其他楼层的澡堂碰碰运气)。故第 $i$ 个人会在当前排队人数在 $[l_i, r_i]$时选择排队。

现在有 $n$ 个人,$q$ 次询问,第 $j$ 次询问给定 $L_j, R_j$,假设当前澡堂没有空位了(所以到了就要排队),问编号为 $L_j,L_j+1,…,R_j$ 的人依次去洗澡,最终会有几个人排队。(假设这些人在排队的这些时候,一直没有人洗完澡空出位置)

形式化题意,给定 $l_i, r_i$, 设分段函数 $f_i(x) = x + [x \in [l_i,r_i]]$,多次询问 $f_R(f_{R-1}…f_L(0)))$

Input

第一行两个正整数 $n,q$。

接下来 $n$ 行,每行两个整数表示 $l_i,r_i$。

接下来 $q$ 行,每行两个整数 $L_j, R_j$ 表示询问。

Output

共 $q$ 行,每行一个整数表示询问的答案。

Example

Input

3 3
0 0
1 2
0 2
1 1
1 3
2 3

Output

1
3
1

Scoring

Subtask1: $n,q \le 5000$,$10\%$。

Subtask2: $n\le 2\times 10 ^ 5$,$L = 1$,$15\%$。

Subtask3: $n\le 2\times 10 ^ 5$,$l_i = 0$,$15\%$。

Subtask4: $n\le 2\times 10 ^ 5$,$r_i = n$,$15\%$。

Subtask5: $n\le 2\times 10 ^ 5$,$15\%$。

Subtask6: 无特殊性质,$30\%$。

对于全部数据,$1\le n, q \le 10^6, 0\le l_i\le r_i\le n, 1\le L_j\le R_j\le n$。