Description

As stated, given a sequence $a$ of $n$ integers, for each specified closed interval $[l, r]$, query the $k$-th smallest value within the interval.

Input Format

The first line contains two integers, the length $n$ of the sequence and the number $m$ of queries.
The second line contains $n$ integers; the $i$-th integer is the $i$-th element $a_i$ of the sequence.
Each of the next $m$ lines contains three integers $l, r, k$, denoting the $k$-th smallest value within the range $[l, r]$.

Output Format

For each query, output one line with a single integer, the answer.

5 5
25957 6405 15770 26287 26465 
2 2 1
3 4 1
4 5 1
1 2 2
4 4 1

6405
15770
26287
25957
26287

Hint

Sample 1 Explanation

$n=5$, the sequence length is $5$, and the sequence from the first term is $\{25957, 6405, 15770, 26287, 26465\}$.

• The first query asks for the first smallest value in $[2, 2]$, which is $6405$.
• The second query asks for the first smallest value in $[3, 4]$, which is $15770$.
• The third query asks for the first smallest value in $[4, 5]$, which is $26287$.
• The fourth query asks for the second smallest value in $[1, 2]$, which is $25957$.
• The fifth query asks for the first smallest value in $[4, 4]$, which is $26287$.

Constraints

• For $10\%$ of the testdata, $1 \leq n,m \leq 10$.
• For $25\%$ of the testdata, $1 \leq n,m \leq 10^3$.
• For $40\%$ of the testdata, $1 \leq n,m \leq 10^5$.
• For $50\%$ of the testdata, $1 \leq n,m \leq 2\times 10^5$, $0\le a_i \leq 2\times 10^5$.
• For all testdata, $1 \leq n,m \leq 2\times 10^5$, $0\le a_i \leq 10^9$, $1 \leq l \leq r \leq n$, $1 \leq k \leq r - l + 1$.

Translated by ChatGPT 5