Ilya Zban 有一个数组 $a_1, a_2, \dots, a_n$。数组的一个片段 $[l \dots r]$ 指的是数组元素 $a_l, a_{l+1}, \dots, a_r$。

Ilya 有 $q$ 个有序三元组 $(l, r, k)$，其中 $1 \le l \le r \le n$ 且 $1 \le k \le r - l + 1$。对于每一个这样的三元组，他要求你回答以下询问：“在片段 $[l \dots r]$ 中，选取 $k$ 个非空且互不相交的子片段，使得这些子片段的元素之和最大，这个最大和是多少？”

输入格式

第一行包含两个整数 $n$ 和 $q$：数组元素的个数和询问的个数 ($1 \le n, q \le 35\,000$)。

第二行包含 $n$ 个空格分隔的整数 $a_1, a_2, \dots, a_n$：给定的数组 ($-35\,000 \le a_i \le 35\,000$)。

接下来的 $q$ 行包含询问。每一行包含三个整数 $l, r, k$：给定的片段范围以及需要选取的非相交子片段的数量 ($1 \le l \le r \le n, 1 \le k \le r - l + 1$)。

输出格式

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

样例

输入格式 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