题目描述

本题译自 eJOI2020 Problem A. Fountain

一个由 $N$ 层储水装置竖直排列的人造喷泉如下图所示，从上到下分别给储水装置编号为 $1$ 到 $N$：

每个储水装置都有其直径、容量和一个阀门，阀门可以向装置内注入任意体积的水。每当装置内水的体积超出了装置容量，多余的水就会向下流向离这个装置最近且直径严格大于这个装置的某装置中，如果没有这样的装置，则水将直接流向最下层的水路中。

你需要回答 $Q$ 个独立的询问，每个询问的格式如下：

如果向 $R_i$ 容器中注入 $V_i$ 升水，最后的水流会在编号为多少的装置处停止？如果水流止于最下层的水路，请输出 $0$。

输入格式

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

接下来 $N$ 行，每行包含两个整数 $D_i,C_i$，分别表示第 $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$ 号装置中的水不会溢出。

数据范围与提示

对于全部数据：

• $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$

详细子任务附加限制与分值如下表所示：