Мы называем число $W$ $k$-лучшим числом последовательности $B_{1 \dots m}$, если существует последовательность $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$, и вам нужно вычислить минимальное $K$-лучшее число для $A_{L \dots R}$.

Напомним, что $C$ является подпоследовательностью $B$ тогда и только тогда, когда мы можем получить $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