Given a sequence $A_1, A_2, \ldots, A_N$ of length $N$. Write a program to execute the following queries:

• l r k: For the subarray $A_l, A_{l+1}, \ldots, A_r$, select $k$ non-empty and non-overlapping subarrays from it, and output the maximum possible sum of the elements of these subarrays.

Input

The first line contains two integers $N$ and $M$, representing the length of the sequence and the number of queries. ($1 \le N, M \le 35{,}000$)

The second line contains $N$ integers $A_1, A_2, \ldots, A_N$. ($-35{,}000 \le A_i < 35{,}000$)

The next $M$ lines each contain a query. ($1 \le l \le r \le N$, $1 \le k \le r - l + 1$)

Output

For each query, output a line with the answer.

Examples

Input 1

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

Output 1

4
6
5
2
-3

Input 2

5 1
7 7 7 7 7
1 5 1

Output 2

35