题目描述
大家都知道喷泉吧？现在有一个喷泉由 N 个圆盘组成，从上到下依次编号为 1∼N，第 i 个圆盘的直径为 Di ，容量为 Ci ，当一个圆盘里的水大于了这个圆盘的容量，那么水就会溢出往下流，直到流入半径大于这个圆盘的圆盘里。如果下面没有满足要求的圆盘，水就会流到喷泉下的水池里。
现在给定Q 组询问，每一组询问这么描述：
向第 Ri 个圆盘里倒入 Vi 的水，求水最后会流到哪一个圆盘停止。
如果最终流入了水池里，那么输出 0。
注意，每个询问互不影响,也就是每次向圆盘倒水前，所有的圆盘中都没有水。
现在给定Q 组询问，每一组询问这么描述：
向第 Ri 个圆盘里倒入 Vi 的水，求水最后会流到哪一个圆盘停止。
如果最终流入了水池里，那么输出 0。
注意，每个询问互不影响,也就是每次向圆盘倒水前，所有的圆盘中都没有水。
输入
第一行两个整数 N,Q 代表圆盘数和询问数。
接下来 N 行每行两个整数 Di ,Ci代表一个圆盘。
接下来Q 行每行两个整数 Ri ,Vi 代表一个询问。
接下来 N 行每行两个整数 Di ,Ci代表一个圆盘。
接下来Q 行每行两个整数 Ri ,Vi 代表一个询问。
输出
Q 行每行一个整数代表询问的答案。
样例输入 Copy
6 5
4 10
6 8
3 5
4 14
10 9
4 20
1 25
6 30
5 8
3 13
2 8
样例输出 Copy
5
0
5
4
2
提示
样例 1 解释
前两个询问的解释如下图所示：
因为每个询问互不影响，对于第三个询问，第 5 个圆盘里的水不会溢出。
数据规模与约定，本题采用捆绑测试。
Subtask 1（30 pts）：N≤1000，Q≤2000。
Subtask 2（30 pts）：Di为严格单调递增序列。
Subtask 3（40 pts）：无特殊限制。
对于100% 的数据：
2≤N≤105 。
1≤Q≤2×105 。
1≤Ci≤1000。
1≤Di ,Vi ≤109 。
1≤Ri ≤N。
本题是洛谷P7167
前两个询问的解释如下图所示：
因为每个询问互不影响，对于第三个询问，第 5 个圆盘里的水不会溢出。
数据规模与约定，本题采用捆绑测试。
Subtask 1（30 pts）：N≤1000，Q≤2000。
Subtask 2（30 pts）：Di为严格单调递增序列。
Subtask 3（40 pts）：无特殊限制。
对于100% 的数据：
2≤N≤105 。
1≤Q≤2×105 。
1≤Ci≤1000。
1≤Di ,Vi ≤109 。
1≤Ri ≤N。
本题是洛谷P7167