Problem Description

There are $n+1$ cups in front of Yuki, numbered from $0$ to $n$. For cups $1$ to $n$, both the capacity and the current amount of juice are fixed: cup $i$ has capacity $a_i$ and currently contains $b_i$ units of juice. Cup $0$ has capacity $10^9$, and the amount of juice in it is not fixed.

Yuki defines operation $i$ as pouring the juice in cup $i-1$ into cup $i$. If at this time the amount of juice in cup $i$ exceeds its capacity, the juice will overflow until the amount of juice in the cup becomes equal to its capacity.

Now Yuki has $q$ queries. The $i$-th query gives two parameters $v_i, p_i$. You need to find: if cup $0$ contains $v_i$ units of juice, then after Yuki performs operations $1,2,\dots,p_i$ in order, how much juice will be in cup $p_i$.

Note that these operations are not actually performed, meaning the queries are independent of each other.

Input Format

This problem contains multiple test cases.

The first line contains two non-negative integers $c,t$, representing the test point ID and the number of test cases. $c=0$ means this test point is the sample.

Then each test case is given as follows:

• The first line contains two non-negative integers $n,q$.
• The next $n$ lines: the $i$-th line contains two non-negative integers $a_i,b_i$.
• The next $q$ lines: the $i$-th line contains two non-negative integers $v_i,p_i$.

Output Format

For each test case:

• Output $q$ lines. The $i$-th line contains one integer, the answer to the $i$-th query.

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

4
8
13

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

8
7
7
1

Hint

Sample 1 Explanation

This sample contains $1$ test case.

For the $1$st query:

• Cup $0$ contains $5$ units of juice. After pouring it into cup $1$, since cup $1$ has capacity $4$ and $5 \gt 4$, the juice overflows. Therefore, cup $1$ finally contains $4$ units of juice.

For the $2$nd query:

• After operation $1$, cup $1$ contains $0$ units of juice.
• After operation $2$, cup $2$ contains $8$ units of juice.

For the $3$rd query:

• After operation $1$, cup $1$ contains $3$ units of juice.
• After operation $2$, cup $2$ contains $9$ units of juice.
• After operation $3$, cup $3$ contains $13$ units of juice.

Constraints

For all testdata:

• $1 \le t \le 3$.
• $1 \le n \le 2\times10^5$, $0 \le q \le 2\times10^5$.
• For all $1 \le i \le n$, $0 \le b_i \le a_i \le 10^9$.
• For all $1 \le i \le q$, $0 \le v_i \le 10^9$, $1 \le p_i \le n$.

::cute-table{tuack}

• Special Property A: for all $1 \le i \lt n$, $a_i \ge a_{i+1}$.
• Special Property B: for all $1 \le i \le n$, $a_i \le a_{i+1}$.
• Special Property C: for all $1 \le i \le n$, $b_i=0$.

Translated by ChatGPT 5