题目描述

大家都知道喷泉吧？现在有一个喷泉由 $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$ 行每行一个整数代表询问的答案。

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

5
0
5
4
2

前两个询问的解释如下图所示：

因为每个询问互不影响，对于第三个询问，第 $5$ 个圆盘里的水不会溢出。

提示

• 对于 $30\%$ 的数据：$N \le 1000$，$Q \le 2000$。
• 对于另外 $30\%$ 的数据：$D_i$ 为严格单调递增序列。
• 对于 $100\%$ 的数据：$2 \le N \le 10^5$，$1 \le Q \le 2 \times 10^5$，$1 \le C_i \le 1000$，$1 \le D_i,V_i \le 10^5$，$1\le R_i \le N$。