Yuki has $n+1$ cups, numbered $0$ to $n$. For cups $1$ through $n$, the capacity and the volume of juice already inside are fixed: the $i$-th cup has a capacity of $a_i$ and contains $b_i$ volume of juice. The $0$-th cup has a capacity of $10^9$, and the volume of juice it contains is variable.

Yuki defines operation $i$ as pouring the juice from the $(i-1)$-th cup into the $i$-th cup. If the volume of juice in the $i$-th cup exceeds its capacity after pouring, the excess juice spills out until the volume of juice in the cup equals its capacity.

Yuki has $q$ queries. Each query $i$ provides two parameters $v_i$ and $p_i$. You need to determine the volume of juice in the $p_i$-th cup after Yuki performs operations $1, 2, \dots, p_i$ sequentially, assuming the $0$-th cup initially contains $v_i$ volume of juice.

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

Input

This problem contains multiple test cases.

The first line contains two non-negative integers $c$ and $t$, representing the test case ID and the number of test cases, respectively. $c=0$ indicates that the test case is a sample.

Each test case is provided as follows:

• The first line contains two non-negative integers $n$ and $q$.
• The next $n$ lines each contain two non-negative integers $a_i$ and $b_i$.
• The next $q$ lines each contain two non-negative integers $v_i$ and $p_i$.

Output

For each test case:

• Output $q$ lines, where the $i$-th line contains an integer representing the answer to the $i$-th query.

Examples

Input 1

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

Output 1

4
8
13

Note 1

This sample contains $1$ test case.

For the first query:

• The $0$-th cup contains $5$ volume of juice. After pouring it into the $1$-st cup, since the $1$-st cup has a capacity of $4$ and $5 > 4$, the juice spills out, so the final volume in the $1$-st cup is $4$.

For the second query:

• After operation $1$, the $1$-st cup contains $0$ volume of juice.
• After operation $2$, the $2$-nd cup contains $8$ volume of juice.

For the third query:

• After operation $1$, the $1$-st cup contains $3$ volume of juice.
• After operation $2$, the $2$-nd cup contains $9$ volume of juice.
• After operation $3$, the $3$-rd cup contains $13$ volume of juice.

Input 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

Output 2

8
7
7
1

Constraints

For all test cases:

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

• Special Property A: For all $1 \le i < 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$.