如果存在一个序列 $C_{1 \dots k}$ 满足以下两个条件，我们称 $W$ 为序列 $B_{1 \dots m}$ 的 $k$-最佳数（$k$-best number）：

1. $C_{1 \dots k}$ 是 $B_{1 \dots m}$ 的子序列。
2. $\forall i \in [1, k], C_i + C_{(i \bmod k)+1} \le W$。

给定一个序列 $A_{1 \dots n}$，你需要回答 $Q$ 个询问。每个询问包含三个整数 $L, R, K$，你需要计算 $A_{L \dots R}$ 的最小 $K$-最佳数。

回想一下，当且仅当可以通过删除 $B$ 中的某些元素（可能不删或全删）得到 $C$ 时，称 $C$ 是 $B$ 的子序列。

输入格式

第一行包含两个整数 $n$ 和 $Q$ ($1 \le n, Q \le 10^5$)。 第二行包含 $n$ 个整数 $A_{1 \dots n}$ ($0 \le A_i \le 10^9$)。 接下来 $Q$ 行，每行包含三个整数 $L, R, K$，代表一个询问 ($1 \le L \le R \le n$; $1 \le K \le R - L + 1$)。

输出格式

对于每个询问，输出一行，包含一个整数：即答案。

样例

输入 1

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

输出 1

8
3
6