题目描述

nz 国的国王来到一块震动的方格。他掏出从 vampire 手里抢来的烛台，却发现自己忘记拿蜡烛了。于是他召唤出一只 djinni，请求给他 7 根蜡烛。

没想到这只 djinni 的前世竟是 H 国国王，因为屠杀 nz 而遭到诅咒，想要得到他的帮助，必须解开 high priest 设下的黑(du)魔(liu)法(ti)。

djinni 有 $n$ 只蜡烛排成一排，第 $i$ 只蜡烛点燃时的亮度为 $a_i$。

现在有 $q$ 个询问，给出三个参数 $l,r,k$，需要在区间 $[l,r]$ 内点燃恰好 $k$ 只蜡烛，且相邻的蜡烛不能同时点燃（保证 $1\le k\le \lceil \frac{r-l+1}2 \rceil$）。求能够得到的最大亮度总和，询问相互独立。

输入格式

第一行两个整数 $n,q$。

第二行 $n$ 个整数表示 $a_i$。

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

输出格式

输出 $q$ 行表示答案。

样例输入

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

样例输出

10
8
8
4
4

数据范围

对于所有数据，满足 $1\le n,q\le 10^5,1\le a_i\le 10^4,1\le k\le \lceil \frac{r-l+1}2 \rceil$。

• 子任务 1（25pts）：$l=1,r=n$
• 子任务 2（25pts）：$k\le 10$
• 子任务 3（25pts）：$q\le 10^4$
• 子任务 4（25pts）：无特殊限制