P15796 【MX-J28-T3】「Cfz Round 8」Juice Problem

Yuki 的面前有 $n+1$ 个杯子，编号依次为 $0$ 至 $n$。其中，第 $1$ 个到第 $n$ 个杯子的容积与装着的果汁的体积是固定的：第 $i$ 个杯子的容积为 $a_i$，装着的果汁的体积为 $b_i$；而第 $0$ 个杯子的容积为 $10^9$，装着的果汁的体积是不固定的。 Yuki 定义，操作 $i$ 为将第 $i-1$ 个杯子装着的果汁倒入到第 $i$ 个杯子中。若此时第 $i$ 个杯子装着的果汁的体积大于杯子的容积，则果汁会溢出去，直到杯子装着的果汁的体积等于杯子的容积。 现在，Yuki 有 $q$ 次询问，第 $i$ 次询问给出第两个参数 $v_i,p_i$。你需要求出，若第 $0$ 个杯子装着的果汁的体积为 $v_i$，在 Yuki 依次执行操作 $1,2,\dots,p_i$ 后，第 $p_i$ 个杯子装着的果汁的体积为多少。 注意，这些操作不会真的被执行，也就是说询问之间相互独立。

**本题包含多组测试数据。** 输入的第一行包含两个非负整数 $c,t$，分别表示测试点编号与测试数据组数。$c=0$ 表示该测试点为样例。 接下来依次输入每组测试数据，对于每组测试数据： - 第一行包含两个非负整数 $n,q$。 - 接下来 $n$ 行，第 $i$ 行包含两个非负整数 $a_i,b_i$。 - 接下来 $q$ 行，第 $i$ 行包含两个非负整数 $v_i,p_i$。

对于每组测试数据： - 输出 $q$ 行，第 $i$ 行包含一个整数，表示第 $i$ 次询问的答案。

### 样例 1 解释 本组样例包含 $1$ 组测试数据。 对于第 $1$ 次询问： - 第 $0$ 个杯子装着的果汁的体积为 $5$，将其倒入到第 $1$ 个杯子中后，由于第 $1$ 个杯子的容积为 $4$ 而 $5\gt 4$，果汁会溢出去，因此最终第 $1$ 个杯子装着的果汁的体积为 $4$。 对于第 $2$ 次询问： - 执行操作 $1$ 后，第 $1$ 个杯子装着的果汁的体积为 $0$； - 执行操作 $2$ 后，第 $2$ 个杯子装着的果汁的体积为 $8$。 对于第 $3$ 次询问： - 执行操作 $1$ 后，第 $1$ 个杯子装着的果汁的体积为 $3$； - 执行操作 $2$ 后，第 $2$ 个杯子装着的果汁的体积为 $9$； - 执行操作 $3$ 后，第 $3$ 个杯子装着的果汁的体积为 $13$。 ### 数据范围 对于所有测试数据，均有： - $1 \le t \le 3$； - $1 \le n \le 2\times10^5$，$0 \le q \le 2\times10^5$； - 对于所有 $1 \le i \le n$，$0 \le b_i \le a_i \le 10^9$； - 对于所有 $1 \le i \le q$，$0 \le v_i \le 10^9$，$1 \le p_i \le n$。 ::cute-table{tuack} | 测试点编号 | $n,q \le$ | 特殊性质 | | :----------: | :-----------: | :------: | | $1\sim3$ | $2\times10^3$ | 无 | | $4$ | $2\times10^5$ | AC | | $5\sim8$ | ^ | A | | $9$ | ^ | BC | | $10\sim13$ | ^ | B | | $14,15$ | ^ | C | | $16 \sim 20$ | ^ | 无 | - 特殊性质 A：对于所有 $1 \le i \lt n$，均有 $a_i \ge a_{i+1}$。 - 特殊性质 B：对于所有 $1 \le i \le n$，均有 $a_i \le a_{i+1}$。 - 特殊性质 C：对于所有 $1 \le i \le n$，均有 $b_i=0$。