题目背景
$ysgh$ 和 $ysgs$ 在进行体育锻炼。
今天他们看到了操场上的树，想到了 OI 中的线段树，想到了使用线段树优化的最大子段和问题。
题目描述
$ysgs$:我会一个最大子段和问题的非常优秀的算法，可以实在是太前沿了，说出来你们也不懂的，还是不说为好。
$ysgh$:你那前沿算法能做啥？
$ysgs$:给你个长度为 $n$ 的序列 $a$，每次询问给你区间$[l,r]$和 $k$，问在$[l,r]$中选择 $k$ 段不交非空连续子段时，选中元素的和的最大值。
$ysgh$ 发现这个问题的确非常前沿，于是交给了你。
输入格式
第一行两个数字 $n,Q$.
接下来一行 $n$ 个数字,第 $i$ 个数字表示 $a[i]$.
接下来 $Q$ 行，一行 $3$ 个数字 $l,r,k$，表示一次询问。
输出格式
Q 行，一行一个数表示答案
样例输入
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
数据范围
| 测试点编号 | n<= | Q<= |
|---|---|---|
| 1 | 10 | 10 |
| 2 | 100 | 100 |
| 3 | 300 | 300 |
| 4-5 | 1000 | 1000 |
| 6-7 | 2000 | 2000 |
| 8-10 | 5000 | 5000 |
| 11-13 | 8000 | 8000 |
| 14-16 | 8000 | 35000 |
| 17-19 | 15000 | 35000 |
| 20-22 | 25000 | 35000 |
| 23-25 | 35000 | 35000 |
对于所有测试点，满足 $1<=n,Q,1<=l<=r<=n,1<=k<=r-l+1, -35000<=a[i]<=35000$。
