#P18203. 1D Galaxy

1D Galaxy

1D Galaxy

一个一维星系中有 nn 个星球,编号为 11 至 nn。在初始时刻 t=0t=0,第 ii 个星球的位置为 xix_i,重量为 wiw_i。重量可以为负数,也可以为 00;不同星球可以位于相同位置。

星球按照以下离散规则运动。在每个整数时刻,所有星球先根据当前状态计算下一步的位置,然后同时移动:

  • 如果严格位于某星球左侧的星球重量总和大于严格位于它右侧的重量总和,它向左移动一个单位;
  • 如果右侧重量总和较大,它向右移动一个单位;
  • 如果两侧重量总和相等,它保持不动。

星球不发生物理碰撞,可以互相穿过。处于同一位置的星球不计入彼此的左侧或右侧。

形式化地,令 xi,tx_{i,t} 表示第 ii 个星球在时刻 tt 的位置,定义

$$W^L_{i,t}=\sum_{j:x_{j,t}<x_{i,t}}w_j,\qquad W^R_{i,t}=\sum_{j:x_{j,t}>x_{i,t}}w_j.$$

则

$$x_{i,t+1}=\begin{cases} x_{i,t}-1,&W^L_{i,t}>W^R_{i,t},\\ x_{i,t}+1,&W^L_{i,t}<W^R_{i,t},\\ x_{i,t},&W^L_{i,t}=W^R_{i,t}. \end{cases}$$

现有 qq 次询问,每次给出时刻 tt 和原星球编号 ii,请输出 xi,tx_{i,t}。

输入格式

第一行两个整数 n,qn,q,满足 1≤n,q≤1051\le n,q\le10^5。

接下来 nn 行,第 ii 行两个整数 xi,wix_i,w_i,满足 −109≤xi,wi≤109-10^9\le x_i,w_i\le10^9。

接下来 qq 行,每行两个整数 t,it,i,满足 0≤t≤1090\le t\le10^9、1≤i≤n1\le i\le n。

本题只有一组输入。询问不保证按时间排序。

输出格式

输出 qq 行,按照输入的询问顺序输出对应星球在对应时刻的位置。

样例

输入:

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