Étant donné une séquence $A_1, A_2, \ldots, A_N$ de longueur $N$. Écrivez un programme pour exécuter les requêtes suivantes :

• l r k : Pour le sous-tableau $A_l, A_{l+1}, \ldots, A_r$, sélectionnez $k$ sous-tableaux non vides et non chevauchants, et affichez la somme maximale possible des éléments de ces sous-tableaux.

Entrée

La première ligne contient deux entiers $N$ et $M$, représentant la longueur de la séquence et le nombre de requêtes. ($1 \le N, M \le 35{,}000$)

La deuxième ligne contient $N$ entiers $A_1, A_2, \ldots, A_N$. ($-35{,}000 \le A_i < 35{,}000$)

Les $M$ lignes suivantes contiennent chacune une requête. ($1 \le l \le r \le N$, $1 \le k \le r - l + 1$)

Sortie

Pour chaque requête, affichez une ligne contenant la réponse.

Exemples

Entrée 1

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

Sortie 1

4
6
5
2
-3

Entrée 2

5 1
7 7 7 7 7
1 5 1

Sortie 2

35