给定一个长度为 $N$ 的数列 $A_1, A_2, \ldots, A_N$。请编写一个程序执行以下查询：

• l r k：对于子数列 $A_l, A_{l+1}, \ldots, A_r$，从中选出 $k$ 个非空且互不重叠的子数列，输出这些子数列元素之和的最大值。

输入格式

第一行包含两个整数 $N$ 和 $M$，分别表示数列的长度和查询的个数。（$1 \le N, M \le 35{,}000$）

第二行包含 $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

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