初めに

この問題はBreaking door keys（LITTLE BREAK ver.）と問題文が同じですが、$K_i$ の制約が異なっています。

問題文

$N$ 個のドアが横一列に並んでいます。ドア $i$ には強さ $S_i$ の鍵が付けられています。

これから、以下の問題について考えます。

これから、$l\leq i\leq r$ を満たすドア $i$ の内 $k$ 個を選び、その鍵を破壊します。

このとき、破壊したドアの鍵の強さの総和だけ体力を消費します。具体的には、ドア $p_1,p_2,...,p_k$ の鍵を壊した時、体力を $\displaystyle\sum_{i=1}^k S_{p_i}$ 消費します。

適切なドアを選んだ時、それらのドアの鍵を壊すために必要な体力の最小値を求めてください。

この問題には $Q$ 個のシチュエーションが考えられます。$i$ 個目のシチュエーションでは $l=L_i,r=R_i,k=K_i$ としてこの問題を答えてください。

制約

• $1\leq N\leq 2\times 10^5$
• $1\leq S_i\leq 10^9$
• $1\leq Q \leq 2\times 10^5$
• $1\leq L_i\leq R_i\leq N$
• $\color{red}{K_i=R_i-L_i+1}$
• 入力はすべて整数

小課題

この問題にはサブタスクによる部分点が設定されています。

入力

$N\ Q$
$S_1\ S_2\ \dotsc\ S_N$
$L_1\ R_1\ K_1$
$L_2\ R_2\ K_2$
$\vdots$
$L_Q\ R_Q\ K_Q$

出力

$Q$ 行出力してください。

$i$ 行目には、$i$ 個目のシチュエーションに対する答えを出力してください。

サンプル

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

13
18
5

6 3
1 6 9 2 3 1
1 2 2
1 3 3
1 6 6

7
16
22

10 10
642323305 764287637 550312118 577593161 37991786 723146696 964957968 527248326 846898844 212337789
8 10 3
4 8 5
7 10 4
9 10 2
7 9 3
2 4 3
6 7 2
3 8 6
3 7 5
6 9 4

1586484959
2830937937
2551442927
1059236633
2339105138
1892192916
1688104664
3381250055
2854001729
3062251834