길이가 $N$인 수열 $A_1, A_2, \ldots, A_N$이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오.

• l r k: 부분수열 $A_l, A_{l+1}, \ldots, A_r$ 에 대해, 해당 부분 수열에서 $k$개의 부분 수열을 골라서 부분 수열의 원소의 합의 최댓값을 출력하라. 고른 부분 수열은 각각 비어있지 않아야 하며, 서로 겹쳐서는 안된다.

입력

첫째 줄에 수열의 크기 $N$, 쿼리의 개수 $M$이 주어진다. ($1 \le N, M \le 35{,}000$)

둘째 줄에는 $A_1, A_2, \ldots, A_N$이 주어진다. ($-35{,}000 \le A_i < 35{,}000$)

셋째 줄부터 $M$개의 줄에는 쿼리가 한 줄에 하나씩 주어진다. ($1 \le l \le r \le N$, $1 \le k \le r - l + 1$)

출력

쿼리의 결과를 한 줄에 하나씩 출력한다.

Sample

Input

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

Output

4
6
5
2
-3

Sample

Input

5 1
7 7 7 7 7
1 5 1

Output

35