Problem Description

Consider a numeric array $b_1, \dots, b_m$. A sliding window of length $k$ ($k \le m$) on this array refers to all subsegments of length $k$, i.e. $\{b_1, \dots, b_k\}$, $\{b_2, \dots, b_{k + 1}\}$, $\dots$, $\{b_{m-k+1}, \dots, b_m\}$.

Given a numeric array $a_1, \dots, a_n$ of length $n$, answer $q$ queries about this array. Each query is as follows: for given $l$, $r$, and $k$, find the sum of the minimum values of all sliding windows of length $k$ on the subsegment $\{a_l, \dots, a_r\}$.

Input Format

The first line 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 in the array.

The next $q$ lines describe 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 sliding window length for the $i$-th query.

Output Format

Output $q$ lines, each containing the answer to the corresponding query. On the $i$-th line, output one number, the sum of the minimum values of all sliding windows of length $k_i$ on the subsegment $\{a_{l_i}, \dots, a_{r_i}\}$.

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

4
9
1

Hint

Translated by ChatGPT 5