Juice Problem

• 时间限制：$1.0$ 秒
• 空间限制：$512\text{ Mib}$

题目描述

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

0 1
3 3
4 0
9 8
13 8
5 1
0 2
3 3

样例 1 输出

4
8
13

样例 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$。

样例 2 输入

0 2
5 3
3 1
6 2
9 3
7 2
8 0
4 3
0 4
1 5
2 1
0 0
3 1
5 2

样例 2 输出

8
7
7
1

数据范围

对于所有测试数据，均有：

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

• 特殊性质 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$。