Dada una secuencia $A_1, A_2, \ldots, A_N$ de longitud $N$. Escribe un programa que ejecute las siguientes consultas:

• l r k: Para el subarreglo $A_l, A_{l+1}, \ldots, A_r$, selecciona $k$ subarreglos no vacíos y que no se superpongan de él, e imprime la suma máxima posible de los elementos de estos subarreglos.

Entrada

La primera línea contiene dos enteros $N$ y $M$, que representan la longitud de la secuencia y el número de consultas. ($1 \le N, M \le 35{,}000$)

La segunda línea contiene $N$ enteros $A_1, A_2, \ldots, A_N$. ($-35{,}000 \le A_i < 35{,}000$)

Las siguientes $M$ líneas contienen cada una una consulta. ($1 \le l \le r \le N$, $1 \le k \le r - l + 1$)

Salida

Para cada consulta, imprime una línea con la respuesta.

Ejemplos

Entrada 1

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

Salida 1

4
6
5
2
-3

Entrada 2

5 1
7 7 7 7 7
1 5 1

Salida 2

35