Yuki の前には $0$ から $n$ までの番号が振られた $n+1$ 個のコップがある。第 $1$ から第 $n$ までのコップには、あらかじめ容積 $a_i$ と中に入っているジュースの体積 $b_i$ が決まっている。一方、第 $0$ 番目のコップの容積は $10^9$ であり、中に入っているジュースの体積は固定されていない。

Yuki は操作 $i$ を、「第 $i-1$ 番目のコップに入っているジュースを第 $i$ 番目のコップに注ぐ」ことと定義する。このとき、第 $i$ 番目のコップに入っているジュースの体積がそのコップの容積を超えた場合、ジュースは溢れ出し、最終的にコップに入っているジュースの体積はコップの容積と等しくなる。

現在、Yuki は $q$ 回の質問を行う。各質問 $i$ では、$2$ つのパラメータ $v_i, p_i$ が与えられる。第 $0$ 番目のコップに $v_i$ の体積のジュースが入っている状態で、Yuki が操作 $1, 2, \dots, p_i$ を順に実行したとき、第 $p_i$ 番目のコップに入っているジュースの体積を求めよ。

なお、これらの操作は実際には実行されず、各質問は独立しているものとする。

入力

本題は複数のテストケースを含む。

入力の最初の行には、$2$ つの非負整数 $c, t$ が含まれる。それぞれテストケースの番号とテストケースの数を示す。$c=0$ はそのテストケースがサンプルであることを示す。

続いて各テストケースが順に入力される。各テストケースの構成は以下の通りである。

• 第 $1$ 行には、$2$ つの非負整数 $n, q$ が含まれる。
• 続く $n$ 行には、第 $i$ 行に $2$ つの非負整数 $a_i, b_i$ が含まれる。
• 続く $q$ 行には、第 $i$ 行に $2$ つの非負整数 $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 > 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 < 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$ が成り立つ。