K-ésimo em Intervalo

#185

Made by: Crazynds

2000MB

Dado um array $A$ de $N$ inteiros, responda $Q$ consultas independentes. Cada consulta fornece três inteiros $l$, $r$ e $k$, e você deve encontrar o $k$-ésimo menor elemento no subarray $A[l..r]$ (considerando os elementos com repetição).

Input

A primeira linha contém dois inteiros $N$ e $Q$ $(1 \le N, Q \le 10^6)$.

A segunda linha contém $N$ inteiros $A_i$ $(-10^9 \le A_i \le 10^9)$.

As próximas $Q$ linhas contêm três inteiros $l$, $r$ e $k$ $(1 \le l \le r \le N,\ 1 \le k \le r - l + 1)$.

Output

Para cada consulta, imprima o $k$-ésimo menor elemento em uma linha separada.

Input Example

Output Example

7 3
3 1 4 1 5 9 2
2 6 3
1 7 1
3 7 4

4
1
5

5 4
10 20 10 30 20
1 5 2
2 4 1
1 3 3
3 5 2

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

3
3
6

6 3
-5 -3 -1 0 2 4
1 6 1
2 5 3
1 6 6

-5
0
4

8 4
5 2 8 1 9 3 7 4
1 8 1
2 6 1
3 7 1
4 8 1

48 13
91 -49 68 -48 10 53 39 -86 -68 98 95 22 -90 86 74 59 28 -57 62 9 -38 91 4 83 -49 77 -93 70 -44 -64 -67 -45 52 23 95 -1 -7 -38 49 -93 -93 88 -25 39 37 -69 30 -89
42 42 1
39 47 6
21 48 22
28 41 14
45 46 1
17 29 10
25 38 10
34 36 1
7 11 2
35 43 1
4 30 7
24 43 3
35 40 1