Cho dãy $A_1, A_2, \ldots, A_N$ độ dài $N$. Viết chương trình thực hiện các truy vấn sau:

• l r k: Với đoạn con $A_l, A_{l+1}, \ldots, A_r$, chọn $k$ đoạn con không rỗng và không giao nhau từ nó, và in ra tổng lớn nhất có thể của các phần tử của các đoạn con này.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên $N$ và $M$, biểu diễn độ dài dãy số và số lượng truy vấn. ($1 \le N, M \le 35{,}000$)

Dòng thứ hai chứa $N$ số nguyên $A_1, A_2, \ldots, A_N$. ($-35{,}000 \le A_i < 35{,}000$)

$M$ dòng tiếp theo, mỗi dòng chứa một truy vấn. ($1 \le l \le r \le N$, $1 \le k \le r - l + 1$)

Dữ liệu ra

Với mỗi truy vấn, in ra một dòng chứa kết quả.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

4
6
5
2
-3

Dữ liệu vào 2

5 1
7 7 7 7 7
1 5 1

Dữ liệu ra 2

35