Statement

Given an integer sequence A of length N, answer Q range queries. Each query gives l,r,k; output the k-th smallest number in A_l,A_{l+1},...,A_r.

This is a template problem for overall binary search with a Fenwick tree.

Input

N Q
A_1 A_2 ... A_N
l_1 r_1 k_1
...
l_Q r_Q k_Q

Output

Print Q lines, one answer per query.

Constraints

• 1 <= N,Q <= 2 * 10^5
• -10^9 <= A_i <= 10^9
• 1 <= l <= r <= N
• 1 <= k <= r-l+1