题目描述

一座新喷泉由 $N$ 个竖直排列的圆形储水池组成。从上到下，储水池依次编号为 $1$ 到 $N$，如下图所示。

每个储水池都有一定的直径和容量，并装有一个水龙头，可以从中放出任意量的水。当流入某个储水池的水量超过其容量时，多出的水会从两侧溢出，向下流入距离它最近、且直径严格大于它的储水池。如果下方不存在这样的储水池，多出的水就会流入排水渠。

你需要回答 $Q$ 次相互独立的询问。每次询问给出 $R_i$ 和 $V_i$，表示从第 $R_i$ 个储水池的水龙头放出 $V_i$ 升水。请输出水流最后停留的储水池编号；如果水流最终流入排水渠，则输出 $0$。

输入格式

从文件 fountain.in 中读入数据。

第一行包含两个整数 $N,Q$。

接下来 $N$ 行，每行包含两个整数 $D_i,C_i$，分别表示第 $i$ 个储水池的直径和容量。

接下来 $Q$ 行，每行包含两个整数 $R_i,V_i$，表示一次询问。

输出格式

将答案输出到文件 fountain.out 中。

输出 $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$ 个储水池不会溢出。

数据范围

• $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^9$；
• $1\le R_i\le N$。

子任务

1. $30$ 分：$N\le 1000$，$Q\le 2000$。
2. $30$ 分：从上到下，储水池的直径严格递增，即 $D_i<D_{i+1}$。
3. $40$ 分：无额外限制。