题目背景

模拟赛偶遇联考，子序列复读强如怪物，拼尽全力无法战胜。

并非偶遇，并非怪物，并非无法战胜。

题目描述

给你一个长度为 $n$ 的序列 $a_{1\dots n}$。

接下来有 $q$ 次查询，每次给出一个区间 $[l,r]$ 和 $k$，你需要：

• 在区间中选择一个长为 $k$ 的子序列，最小化相邻两项的和的最大值。

形式化地说，选择一组 $l\le p_1 <p_2 <\dots <p_k \le r$，最小化 $\displaystyle\max_{i=1}^{k-1} (a_{p_i}+a_{p_{i+1}})$。

输入格式

第一行两个整数 $n,q$。

第二行 $n$ 个整数 $a_{1\dots n}$。

接下来 $q$ 行，每行 $3$ 个整数 $l,r,k$ 表示一次询问。

输出格式

共 $q$ 行，每行一个整数表示答案。

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

9
9
4
4
6
4

提示

数据范围与约定

本题采用捆绑测试。

::cute-table | 子任务编号 | $n\le$ | $q\le$ | 特殊性质 | 分值 | | :----------: | :----------: | :----------: | :----------: | :----------: | | $1$ | $18$ | $18$ | 无 | $5$ | | $2$ | $40$ | $2\times10^5$ | ^ | $10$ | | $3$ | $1000$ | $1000$ | ^ | $5$ | | $4$ | $10^5$ | $10$ | ^ | $20$ | | $5$ | ^ | $2\times 10^5$ | $a_i\le 2$ | $15$ | | $6$ | ^ | ^ | $a_i\le 5$ | $15$ | | $7$ | ^ | ^ | 无 | $25$ | | $8$ | $3\times 10^5$ | $3\times 10^5$ | ^ | $5$ |

对于所有数据，保证 $1\le n,q\le 3\times 10^5$，$1\le a_i \le n$，$1\le l\le r\le n$，$2\le k\le r-l+1$。

保证你在本场模拟赛的得分不超过 $\bm{998244853}$。