题目描述

Ilya Zban 有一个长度为 $n$ 的数组

数组的一个区间 $[l\ldots r]$ 指连续数组

Ilya 准备了 $q$ 个询问，每个询问是一个有序三元组 $(l,r,k)$。对于这个询问，你需要在区间 $[l\ldots r]$ 中选择 $k$ 个非空且互不相交的连续子段，使这些子段的元素和之和尽可能大。

请对每个询问输出这个最大值。

输入格式

第一行包含两个整数 $n,q$，分别表示数组长度和询问数量。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

接下来 $q$ 行，每行包含三个整数 $l,r,k$，表示一个询问。

输出格式

输出 $q$ 行，每行一个整数，依次表示每个询问的答案。

数据范围

• $1\le n,q\le 35000$；
• $-35000\le a_i\le 35000$；
• $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

输出

4
6
5
2
-3

样例 2

输入

5 1
7 7 7 7 7
1 5 1

输出

35