Consider an array of numbers $b_1, \dots, b_m$. We define sliding windows of length $k$ ($k \le m$) on this array as all subsegments of length $k$, that is, the segments $[b_1, \dots, b_k], [b_2, \dots, b_{k+1}], \dots, [b_{m-k+1}, \dots, b_m]$.

Given an array of numbers $a_1, \dots, a_n$ of length $n$.

You need to answer $q$ queries of the following type regarding this array: for given $l, r, k$, find the sum of the minimums of all sliding windows of length $k$ within the subsegment $[a_l, \dots, a_r]$.

Input

The first line of input contains two integers $n$ and $q$ ($1 \le n, q \le 100\,000$) — the length of the array and the number of queries.

The second line contains $n$ integers $a_1, \dots, a_n$ ($1 \le a_i \le 10^9$) — the values of the numbers in the array.

The next $q$ lines contain the queries. The $i$-th line contains three integers $l_i, r_i$, and $k_i$ ($1 \le l \le r \le n$, $1 \le k \le r - l + 1$) — the left and right boundaries of the subsegment and the length of the sliding window in the $i$-th query.

Output

Output $q$ lines with the answers to the queries. In the $i$-th line, output a single number — the sum of the minimums of the sliding windows of length $k_i$ on the subsegment $[a_{l_i}, \dots, a_{r_i}]$.

Subtasks

Examples

Input 1

6 3
4 6 1 2 5 3
2 5 2
2 4 1
1 6 6

Output 1

4
9
1