A - K-ésimo número

Languages: C, C++, Java, JavaScript, Haskell, Tiger, Python, Pascal, C#
Time & Memory limits: (details)

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)

Input
7 3 1 5 2 6 3 7 4 2 5 3 4 4 1 1 7 3
Output
5 6 3