与えられた長さ $N$ の数列 $A_1, A_2, \ldots, A_N$ に対して、以下のクエリを実行するプログラムを書いてください。

• l r k: 部分列 $A_l, A_{l+1}, \ldots, A_r$ から、空でなく重複しない $k$ 個の部分列を選び、それらの要素の和の最大値を出力してください。

入力

1 行目には、数列の長さ $N$ とクエリの個数 $M$ が与えられる。 ($1 \le N, M \le 35{,}000$)

2 行目には、$N$ 個の整数 $A_1, A_2, \ldots, A_N$ が与えられる。 ($-35{,}000 \le A_i < 35{,}000$)

次の $M$ 行には、それぞれクエリが与えられる。 ($1 \le l \le r \le N$, $1 \le k \le r - l + 1$)

出力

各クエリについて、答えを 1 行に出力してください。

入出力例

入力 1

5 5
-1 2 -3 4 -5
1 5 1
1 5 2
1 5 3
1 5 4
1 5 5

出力 1

4
6
5
2
-3

入力 2

5 1
7 7 7 7 7
1 5 1

出力 2

35