我們稱一個序列 $B_{1 \dots m}$ 的 $k$-最佳數（$k$-best number）為 $W$，若存在一個序列 $C_{1 \dots k}$ 滿足以下兩個條件：

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$-最佳數。

回顧一下，$C$ 是 $B$ 的子序列，若且唯若我們可以透過移除 $B$ 中的某些元素（可能為零個或全部）來得到 $C$。

輸入格式

第一行包含兩個整數 $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