Matcom Online Grader

Estas trabajando para la compañía Macrosoft en el departamento de estructura de datos. El jefe de departamento pide que programes una estructura de dato que sea capaz de buscar el k-ésimo elemento en segmentos de una lista.

Dado una lista $a[1... N]$ de enteros diferentes, tu programa debe responder una serie de preguntas $Q(i, j, k)$ de la forma: ¿Cuál es el k-ésimo numero en el segmento $a[i... j]$, si este segmento estuviese ordenado?

Por ejemplo, considera la lista $a = (1, 5, 2, 6, 3, 7, 4)$. Sea la pregunta $Q(2, 5, 3)$. El segmento $a[2 … 5]$ es $(5, 2, 6, 3)$. Si estuviera ordenado, tendríamos $(2, 3, 5, 6)$, el tercer elemento es $5$ y por tanto la respuesta a la pregunta anterior seria $5$.

Input

La primera línea de la entrada contiene a $N$ – el tamaño de la lista, y $M$ – el número de preguntas a responder $(1 \leq N \leq 100000, 1 \leq M \leq 5000)$.

La segunda línea contiene $N$ enteros diferentes que no exceden $10^9$ por su valor absoluto – la descripción de la lista.

Las siguientes $M$ líneas contienen la descripción de las preguntas, cada descripción consiste de tres números $i$, $j$ y $k$ $(1 \leq i \leq j \leq N, 1 \leq k \leq j - i + 1)$ y representan la pregunta $Q(i, j, k)$.

Output

Por cada pregunta la respuesta correspondiente – el k-ésimo número en el segmento ordenado $a[i ... j]$.

Sample test(s)