Ilya Zban 有一个数组 $a_1, a_2, \ldots, a_n$ 。数组的 $[l \ldots r]$ 段是数组 $a_l, a_{l + 1}, \ldots, a_r$ 。 伊利亚有 $q$ 个有序三元组，其形式为 $(l, r, k)$ ，其中 $1 \leq l \leq r \leq n$ 和 $1 \leq k \leq r - l + 1$ 。

对于每个这样的三元组，他都要求你回答下面的问题："线段 $[l \ldots r]$ 的非空非相交子线段 $k$ 的元素之和的最大值是多少？

输入

第一行输入包含两个整数 $n$ 和 $q$ ：数组中的元素个数和查询次数（ $1 \leq n, q \leq 35\,000$ ）。

第二行包含 $n$ 个空格分隔的整数 $a_1, a_2, \ldots, a_n$ ：给定数组（ $-35\,000 \leq a_i \leq 35\,000$ ）。

接下来的 $q$ 行包含查询。每一行都包含三个整数 $l$ 、 $r$ 、 $k$ ：给定的线段以及在其上应该找到的不相交子线段的数量（ $1 \leq l \leq r \leq n$ 、 $1 \leq k \leq r-l+1$ ）。

输出

分行输出 $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

5 1
7 7 7 7 7
1 5 1

35

子任务划分

• 子任务1：（10 分）— n ≤ 200, q ≤ 200。
• 子任务2：（20 分）— n ≤ 5000, q ≤ 5000, k ≤ 3。
• 子任务3：（15 分）— n ≤ 35000, q ≤ 200。
• 子任务4：（20 分）— n ≤ 35000, q ≤ 35000, a_i ≥ 0。
• 子任务5：（35 分）— n ≤ 35000, q ≤ 35000。