On appelle $W$ un $k$-best number d'une séquence $B_{1 \dots m}$ s'il existe une séquence $C_{1 \dots k}$ satisfaisant les deux conditions suivantes :

1. $C_{1 \dots k}$ est une sous-séquence de $B_{1 \dots m}$.
2. $\forall i \in [1, k], C_i + C_{(i \bmod k)+1} \le W$.

Étant donné une séquence $A_{1 \dots n}$, vous devez répondre à $Q$ questions. Chaque question consiste en trois entiers $L, R, K$, et vous devez calculer le $k$-best number minimum de $A_{L \dots R}$.

Rappelons que $C$ est une sous-séquence de $B$ si et seulement si nous pouvons obtenir $C$ en supprimant certains éléments de $B$ (éventuellement aucun ou tous).

Entrée

La première ligne contient deux entiers $n$ et $Q$ ($1 \le n, Q \le 10^5$). La seconde ligne contient $n$ entiers $A_{1 \dots n}$ ($0 \le A_i \le 10^9$). Ensuite, $Q$ lignes suivent. Chacune d'elles contient trois entiers $L, R, K$, représentant une question ($1 \le L \le R \le n$ ; $1 \le K \le R - L + 1$).

Sortie

Pour chaque question, affichez une seule ligne contenant un seul entier : la réponse.

Exemples

Entrée 1

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

Sortie 1

8
3
6