考虑一个包含 $m$ 个数的数组 $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$ 的滑动窗口的最小值之和。
子任务
| 子任务 | 分值 | 附加限制 | 依赖的子任务 |
|---|---|---|---|
| 1 | 6 | $n, q \le 300$ | |
| 2 | 12 | $n, q \le 4000$ | 1 |
| 3 | 8 | $n, q \le 10\,000$ | 1, 2 |
| 4 | 11 | $n \le 4000$ | 1, 2 |
| 5 | 10 | 所有询问中的 $k_i$ 均相等 | |
| 6 | 14 | $a_i \le 2$ | |
| 7 | 7 | $a_i \le 20$ | 6 |
| 8 | 15 | $l_i = 1, r_i = n$ | |
| 9 | 17 | 无 | 1–8 |
样例
输入样例 1
6 3 4 6 1 2 5 3 2 5 2 2 4 1 1 6 6
输出样例 1
4 9 1