Дана последовательность $A_1, A_2, \ldots, A_N$ длины $N$. Напишите программу, выполняющую следующие запросы:

• l r k: Для подмассива $A_l, A_{l+1}, \ldots, A_r$ выберите $k$ непустых непересекающихся подмассивов и выведите максимально возможную сумму элементов этих подмассивов.

Входные данные

Первая строка содержит два целых числа $N$ и $M$, обозначающих длину последовательности и количество запросов. ($1 \le N, M \le 35{,}000$)

Вторая строка содержит $N$ целых чисел $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$)

Выходные данные

Для каждого запроса выведите строку с ответом.

Примеры

Входные данные 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