Description

老鼠是個天才兒童,在三歲時養了一隻貓咪,在五歲時學會了 LCT,七歲時成功用魔法趕走了兇巴巴的史萊姆,最近則順利拿到書卷獎。
貓咪每天都要舉 1000kg 的槓鈴,只是今天老鼠把槓鈴放在磅秤上後,發現槓鈴竟然少了 24g。

於是老鼠帶貓咪去地下格鬥場,總共有 $n+1$ 個選手,編號為 $0\sim n$。
編號 $i$($0\leq i\leq n$)的選手的體力為 $a_i$,一開始編號 $0$ 的選手為衛冕者,剩下的選手會按照編號由小到大依序向衛冕者挑戰。

假設衛冕者的體力為 $x$,挑戰者的體力為 $y$,若 $x\geq y$,則挑戰者挑戰失敗,衛冕者繼續衛冕,且體力變成 $x-y$;若 $x<y$,則挑戰者挑戰成功,成為衛冕者,且體力變成 $y-x$。

$a_1\sim a_n$ 是固定的,但是 $a_0$ 會隨著編號 $0$ 參賽者的心情改變,貓咪總共有 $q$ 個疑問:如果編號 $0$ 的參賽者體力是 $a_0$,並且現在編號 $p$ 的選手挑戰完了,那麼此時衛冕者的體力是多少?

Input Format

第一行有兩個正整數 $n,q$,代表有 $n+1$ 位選手和 $q$ 個疑問。
第二行有 $n$ 個非負整數 $a_1\sim a_n$,代表編號 $1\sim n$ 選手的體力。
接下來 $q$ 行,每行有一個非負整數和一個正整數 $a_0,p$,代表編號 $0$ 選手的體力和現在編號 $p$ 的選手挑戰完了。

對於所有測試資料:

  • $1\leq n,q\leq 10^ 6$
  • $0\leq a_i\leq 10^ 6$($1\leq i\leq n$)
  • $0\leq a_0\leq 10^ 6$
  • $1\leq p\leq n$

Output Format

對於每個疑問,回答若編號 $0$ 的參賽者體力是 $a_0$,且現在編號 $p$ 的選手挑戰完了,此時衛冕者的體力是多少。

Sample Input 1

3 4
7 10 2
2 1
13 2
20 2
5 3

Sample Output 1

5
4
3
6

Hints

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0 範例測資 0
2 0~5 $n,q\le 3000$ 17
3 1, 6~10 $a_i\le a_{i+1}$($0\le i<n$) 19
4 0~15 無其他限制 64

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 2500 262144 65536 1 2 4
1 2500 262144 65536 2 3 4
2 2500 262144 65536 2 4
3 2500 262144 65536 2 4
4 2500 262144 65536 2 4
5 2500 262144 65536 2 4
6 2500 262144 65536 3 4
7 2500 262144 65536 3 4
8 2500 262144 65536 3 4
9 2500 262144 65536 3 4
10 2500 262144 65536 3 4
11 2500 262144 65536 4
12 2500 262144 65536 4
13 2500 262144 65536 4
14 2500 262144 65536 4
15 2500 262144 65536 4