ある数列 $B_{1 \dots m}$ に対して、以下の2つの条件を満たす数列 $C_{1 \dots k}$ が存在するとき、その値 $W$ を $k$-best number と呼ぶことにします。

1. $C_{1 \dots k}$ は $B_{1 \dots m}$ の部分列である。
2. すべての $i \in [1, k]$ に対して、$C_i + C_{(i \bmod k) + 1} \le W$ が成り立つ。

数列 $A_{1 \dots n}$ が与えられます。$Q$ 個の質問に答えてください。各質問は3つの整数 $L, R, K$ からなり、$A_{L \dots R}$ の最小の $K$-best number を計算する必要があります。

$C$ が $B$ の部分列であるとは、$B$ からいくつかの要素（0個でもすべてでもよい）を取り除くことで $C$ が得られることを指します。

入力

1行目には2つの整数 $n$ と $Q$ ($1 \le n, Q \le 10^5$) が含まれます。 2行目には $n$ 個の整数 $A_{1 \dots n}$ ($0 \le A_i \le 10^9$) が含まれます。 続く $Q$ 行の各行には、質問を表す3つの整数 $L, R, K$ ($1 \le L \le R \le n$; $1 \le K \le R - L + 1$) が含まれます。

出力

各質問に対して、答えとなる整数を1行に出力してください。

入出力例

入力 1

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

出力 1

8
3
6