Dany jest ciąg $A_1, A_2, \ldots, A_N$ o długości $N$. Napisz program wykonujący następujące zapytania:

• l r k: Dla podciągu $A_l, A_{l+1}, \ldots, A_r$ wybierz z niego $k$ niepustych i nienachodzących na siebie podciągów i wypisz maksymalną możliwą sumę elementów tych podciągów.

Wejście

Pierwszy wiersz zawiera dwie liczby całkowite $N$ i $M$, oznaczające długość ciągu oraz liczbę zapytań. ($1 \le N, M \le 35\,000$)

Drugi wiersz zawiera $N$ liczb całkowitych $A_1, A_2, \ldots, A_N$. ($-35\,000 \le A_i < 35\,000$)

Następne $M$ wierszy zawiera po jednym zapytaniu. ($1 \le l \le r \le N$, $1 \le k \le r - l + 1$)

Wyjście

Dla każdego zapytania wypisz wiersz z odpowiedzią.

Przykład

Wejście 1

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

Wyjście 1

4
6
5
2
-3

Wejście 2

5 1
7 7 7 7 7
1 5 1

Wyjście 2

35