구간 K번째 원소

길이 $N$의 정수 수열 $A$가 주어진다. 각 질의 $(l,r,k)$에 대해 부분수열 $A_l,A_{l+1},\cdots,A_r$에서 $k$번째로 작은 값을 출력하여라. 중복된 값은 각각 별개의 원소로 센다.

입력은 다음과 같은 형식으로 주어진다.

$N\ Q$ $A_1\ A_2\ \cdots\ A_N$ $l_1\ r_1\ k_1$ $l_2\ r_2\ k_2$ $\vdots$ $l_Q\ r_Q\ k_Q$

각 질의의 답을 한 줄에 하나씩 출력한다.

• $1 \leq N,Q \leq 100\ 000$.
• $-10^9 \leq A_i \leq 10^9$ ($1 \leq i \leq N$).
• $1 \leq l_j \leq r_j \leq N$ ($1 \leq j \leq Q$).
• $1 \leq k_j \leq r_j-l_j+1$ ($1 \leq j \leq Q$).