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

每个蓄水池都有其直径、容量以及一个可以释放池内任意水量水的阀门。每当水量超过蓄水池的容量时，多余的水会从侧面溢出，并向下流入最靠近的、直径严格大于当前蓄水池的蓄水池中；如果没有这样的蓄水池，水则会流入水道。

你需要回答 $Q$ 个独立的查询：如果你从第 $R_i$ 个蓄水池的阀门释放 $V_i$ 升水，水流最终会停在哪个蓄水池？如果水流最终流入水道，则答案为 $0$。

输入格式

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

输出格式

输出 $Q$ 行，每行一个整数，表示按给定顺序对每个查询的回答。

数据范围

• $2 \le N \le 10^5$
• $1 \le Q \le 2 \cdot 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 分)：无附加限制

样例

样例输入 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

说明

前两个查询如上图所示。 由于查询之间是相互独立的，对于第三个查询，第五个蓄水池不会溢出。