题目描述

有一个喷泉由 $N$ 个圆盘组成，从上到下以此编号为 $1 \sim N$ ，第 $i$ 个喷泉的直径为 $D_{i}$ ，容量为 $C_{i}$ ，当一个圆盘里的水大于了这个圆盘的容量，那么水就会溢出往下流，直到流入半径严格大于溢出圆盘的下层圆盘里。如果下面没有满足要求的圆盘，水就会直接流到喷泉下的水池里。

现在给定 $Q$ 组独立的询问，每一组询问这么描述:

• 向第 $R_{i}$ 个圆盘里倒入 $V_{i}$ 的水, 求水最后会流到哪一个圆盘停止。

如果最终流入了水池里，那么输出 0 。

输入格式

第一行两个整数 $N, Q$ 代表圆盘数和询问数。

接下来 $N$ 行每行两个整数 $D_{i}, C_{i}$ 代表一个圆盘。

接下来 $Q$ 行每行两个整数 $R_{i}, V_{i}$ 代表一个询问。

输出格式

$Q$ 行每行一个整数代表询问的答案。

样例 #1

样例输入 #1

6 5
4 10
6 8
3 5
4 14
10 9
4 20
1 25
6 30
5 8
3 13
2 8

样例输出 #1

5
0
5
4
2

样例 1 的前两个询问的图大致如下:

因为询问相互独立，所以对于第三个询问， 5 号圆盘是不会溢出的。

数据范围

本题采用捆绑测试。

• Subtask 1 (30 pts) : $N \leq 1000, Q \leq 2000$ 。
• Subtask 2 (30 pts) : $D_{i}$ 为严格单调递增序列。
• Subtask 3 (40 pts)：无特殊限制。

对于 $100 \%$ 的数据：

• $2 \leq N \leq 10^{5}$ 。
• $1 \leq Q \leq 2 \times 10^{5}$ 。
• $1 \leq C_{i} \leq 1000$ 。
• $1 \leq D_{i}, V_{i} \leq 10^{9}$ 。
• $1 \leq R_{i} \leq N_{\text {。 }}$