题目描述

评审团需要从一段候选序列中选出若干人组成一个环形队列。若选出的序列为 C_1, C_2, ..., C_k，它必须是原序列的一个子序列，也就是说只能删除一些元素，不能改变剩余元素的相对顺序。

对于一个整数 W，如果存在一个长度为 k 的子序列 C，满足环上任意相邻两人的数值和都不超过 W，即：

C_i + C_{(i mod k) + 1} <= W    对所有 1 <= i <= k

那么称 W 是该序列的一个 k-best 数。

给定长度为 n 的序列 A，你需要回答 Q 个询问。每个询问给出 L, R, K，要求计算区间序列 A_L, A_{L+1}, ..., A_R 的最小 K-best 数。

输入格式

第一行包含两个整数 n, Q，分别表示序列长度和询问数量。

第二行包含 n 个整数 A_1, A_2, ..., A_n。

接下来 Q 行，每行包含三个整数 L, R, K，表示一个询问。

输出格式

对每个询问，输出一行一个整数，表示最小的 K-best 数。

数据范围

• 1 <= n, Q <= 100000
• 0 <= A_i <= 10^9
• 1 <= L <= R <= n
• 1 <= K <= R - L + 1

样例

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

8
3
6