Llamamos a $W$ un $k$-best number de una secuencia $B_{1 \dots m}$ si existe una secuencia $C_{1 \dots k}$ que satisface las siguientes dos condiciones:

1. $C_{1 \dots k}$ es una subsecuencia de $B_{1 \dots m}$.
2. $\forall i \in [1, k], C_i + C_{(i \bmod k)+1} \leq W$.

Dada una secuencia $A_{1 \dots n}$, debes responder $Q$ preguntas. Cada pregunta consiste en tres enteros $L, R, K$, y necesitas calcular el mínimo $k$-best number de $A_{L \dots R}$.

Recuerda que $C$ es una subsecuencia de $B$ si y solo si podemos obtener $C$ eliminando algunos elementos de $B$ (posiblemente ninguno o todos).

Entrada

La primera línea contiene dos enteros $n$ y $Q$ ($1 \leq n, Q \leq 10^5$).

La segunda línea contiene $n$ enteros $A_{1 \dots n}$ ($0 \leq A_i \leq 10^9$).

Luego siguen $Q$ líneas. Cada una de ellas contiene tres enteros $L, R, K$, representando una pregunta ($1 \leq L \leq R \leq n$; $1 \leq K \leq R - L + 1$).

Salida

Para cada pregunta, imprime una sola línea con un único entero: la respuesta.

Ejemplos

Entrada 1

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

Salida 1

8
3
6