题目描述

考虑一个数字数组 $b_1, \dots, b_m$。该数组上长度为 $k$（$k \le m$）的滑动窗口是指所有长度为 $k$ 的子段，即 $\{b_1, \dots, b_k\},$ $\{b_2, \dots, b_{k + 1}\},$ $\dots,$ $\{b_{m-k+1}, \dots, b_m\}$。

给定一个长度为 $n$ 的数字数组 $a_1, \dots, a_n$。回答关于该数组的 $q$ 个查询，查询形式如下：对于给定的 $l$、$r$、$k$，找出子段 $\{a_l, \dots, a_r\}$ 上所有长度为 $k$ 的滑动窗口的最小值之和。

输入格式

输入的第一行包含两个整数 $n$ 和 $q$（$1 \le n, q \le 100\,000$）—— 数组的长度和查询的数量。

第二行包含 $n$ 个整数 $a_1, \dots, a_n$（$1 \le a_i \le 10^9$）—— 数组中数字的值。

接下来的 $q$ 行包含查询。第 $i$ 行给出三个整数 $l_i$、$r_i$ 和 $k_i$（$1 \le l \le r \le n$，$1 \le k \le r - l + 1$）—— 第 $i$ 个查询的子段左右边界以及滑动窗口的长度。

输出格式

输出 $q$ 行，每行包含对应查询的答案。第 $i$ 行输出一个数字 —— 子段 $\{a_{l_i}, \dots, a_{r_i}\}$ 上所有长度为 $k_i$ 的滑动窗口的最小值之和。

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

4
9
1

提示