JOI 村には N 個の区画があり，1 から N までの番号が付いている．これらの区画は番号順に一列に並んでいる．今，各区画では火事が発生しており，時刻 0 における区画 i (1 \leqq i \leqq N) の火の強さは S_i (S_i > 0) である．

時刻 0 に，区画 1 から区画 N の方向に風が吹き始めた．隣り合う 2 つの区画について，時刻 t (0 \leqq t) において風上の区画の火が風下の区画の火より強いとき，時刻 t + 1 における風下の区画の火の強さは，時刻 t における風上の区画の火の強さと同じになってしまう．そうでないときは，時刻 t + 1 における風下の区画の火の強さは，時刻 t と同じである．すなわち，時刻 t (0 \leqq t) における区画 i (1 \leqq i \leqq N) の火の強さを S_i(t) と書くとすると，1 \leqq t ならば，S_i(t) = \max\{S_{i − 1}(t − 1), S_i(t − 1)\} となる．ただし，任意の t (0 \leqq t) に対して，S_0(t) = 0 とし，任意の i (1 \leqq i \leqq N) に対し S_i(0) = S_i とする．

消防士であるあなたは Q 個の消火活動を計画した．Q 個の計画のうちどれか 1 つだけを実施する予定である．j 番目の計画 (1 \leqq j \leqq Q) は，時刻 T_j に，L_j \leqq k \leqq R_j となるすべての区画 k に消火剤を撒き，それらの区画を消火するというものである．火の強さが s である区画を消火するためには s リットルの消火剤が必要である．つまり，j 番目の計画の消火活動には S_{L_j}(T_j) + S_{L_j + 1}(T_j) + \cdots + S_{R_j}(T_j) リットルの消火剤が必要である．

どの計画を実行するか吟味するためにも，各計画に必要な消火剤の量が知りたい．

時刻 0 における火の強さの情報と消火活動の計画の情報が与えられたとき，各計画に必要な消火剤の量を求めるプログラムを作成せよ．

制約

• 1 \leqq N \leqq 200\,000．
• 1 \leqq Q \leqq 200\,000．
• 1 \leqq S_i \leqq 1\,000\,000\,000 (1 \leqq i \leqq N)．
• 1 \leqq T_j \leqq N (1 \leqq j \leqq Q)．
• 1 \leqq L_j \leqq R_j \leqq N (1 \leqq j \leqq Q)．

小課題

1. (1 点) N \leqq 200，Q \leqq 200．
2. (6 点) T_1 = T_2 = \cdots = T_Q．
3. (7 点) L_j = R_j (1 \leqq j \leqq Q)．
4. (6 点) S_i \leqq 2 (1 \leqq i \leqq N)．
5. (80 点) 追加の制約はない．

入力例 1

5 5
9 3 2 6 5
1 1 3
2 1 5
3 2 5
4 3 3
5 3 5

出力例 1

21
39
33
9
27

• 時刻 0 における各区画の火の強さは，区画 1 から順に 9, 3, 2, 6, 5 である．
• 時刻 1 における各区画の火の強さは，区画 1 から順に 9, 9, 3, 6, 6 である．よって，1 番目の計画に必要な消火剤の量は 9 + 9 + 3 = 21 リットルである．
• 時刻 2 における各区画の火の強さは，区画 1 から順に 9, 9, 9, 6, 6 である．よって，2 番目の計画に必要な消火剤の量は 9 + 9 + 9 + 6 + 6 = 39 リットルである．
• 時刻 3 における各区画の火の強さは，区画 1 から順に 9, 9, 9, 9, 6 である．よって，3 番目の計画に必要な消火剤の量は 9 + 9 + 9 + 6 = 33 リットルである．
• 時刻 4 における各区画の火の強さは，区画 1 から順に 9, 9, 9, 9, 9 である．よって，4 番目の計画に必要な消火剤の量は 9 リットルである．
• 時刻 5 における各区画の火の強さは，区画 1 から順に 9, 9, 9, 9, 9 である．よって，5 番目の計画に必要な消火剤の量は 9 + 9 + 9 = 27 リットルである．

入力例 1 は小課題 1, 5 の制約を満たす．

入力例 2

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

出力例 2

28
21
34
4
64
43
55
9
27
9

入力例 2 は小課題 1, 5 の制約を満たす．

入力例 3

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

出力例 3

9
9
3
4
3
4
5
9
9
9

入力例 3 は小課題 1, 3, 5 の制約を満たす．

入力例 4

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

出力例 4

28
27
34
4
64
43
55
9
27
9

入力例 4 は小課題 1, 2, 5 の制約を満たす．

入力例 5

20 20
2 1 2 2 1 1 1 1 2 2 2 1 2 1 1 2 1 2 1 1
1 1 14
2 3 18
4 10 15
8 2 17
9 20 20
4 8 19
7 2 20
11 1 5
13 2 8
20 1 20
2 12 15
7 1 14
12 7 18
14 2 17
9 19 20
12 12 12
6 2 15
11 2 15
19 12 17
4 1 20

出力例 5

25
30
12
32
2
24
38
10
14
40
8
28
24
32
4
2
28
28
12
40

入力例 5 は小課題 1, 4, 5 の制約を満たす．