题目描述

在一个神奇的一维空间内有 $n$ 个星球，从 $1$ 到 $n$ 编号。初始（$t=0$）时编号为 $i$ 的星球位于 $x_i$ 位置，重量为 $w_i$（可以为负数）。现实中的星球会在万有引力的作用下运动，而这个一维星系中的星球也会因为吸引而产生运动，但其规律与现实中的物理法则并不相同。具体地说，对于这个一维星系中的任意一个星球，如果其左边的星球重量总和大于其右边的星球重量总和，那么它下一时刻会往左移动一个单位；如果右边大于左边，那么它下一时刻会往右移动一个单位；如果二者相等，那么它下一时刻的位置保持不变。你可以认为这个星系中的星球不发生任何物理碰撞，即可以互相穿过。

形式化地说，令编号为 $i$ 的星球在时刻 $t$ ($t = 0, 1, 2, \ldots$) 的位置为 $x_{i,t}$，该时刻其左边的星球重量总和为 $w_{i,t}^l = \sum_{j\ :\ x_{j,t} < x_{i,t}} w_j$，其右边的星球重量总和为 $w_{i,t}^r = \sum_{j\ :\ x_{j,t} > x_{i,t}} w_j$。该星球下一时刻的位置 $x_{i, t+1}$ 满足：

$$x_{i, t+1} = \begin{cases} x_{i,t} - 1, & w_{i,t}^l > w_{i,t}^r \\ x_{i,t} + 1, & w_{i,t}^l < w_{i,t}^r \\ x_{i,t}, & w_{i,t}^l = w_{i,t}^r \end{cases}$$

现在有 $q$ 个询问，每个询问形如「查询时刻 $t$ 时编号为 $i$ 的星球所在的位置」。请回答这些询问。

输入格式

第一行两个整数 $n$ 和 $q$ ($1 \le n, q \le 10^5$)，分别表示星球个数和询问个数。

接下来 $n$ 行，第 $i$ 行两个整数 $x_i, w_i$ ($-10^9 \le x_i, w_i \le 10^9$)，分别表示编号为 $i$ 的星球的初始位置和重量。

接下来 $q$ 行，每行两个整数 $t$ 和 $i$ ($0 \le t \le 10^9$, $1 \le i \le n$)，表示一次询问。

输出格式

输出 $q$ 行，依次表示对每个询问的回答。

4 12
0 1
1 2
-1 3
2 2
0 1
0 2
0 3
0 4
1 1
1 2
1 3
1 4
2 1
2 2
2 3
2 4

0
1
-1
2
1
0
0
1
0
1
1
0