Given a sequence A of N pairwise-distinct integers. There are Q queries L R K, asking for the k-th element in the increasing-sorted subsequence A[L], A[L+1], ...., A[R-1], A[R]. The original sequence never changes.
1 ≤ N, Q ≤ 10^5
|Ai| ≤ 10^9, 1 ≤ i ≤ N
1 ≤ L ≤ R ≤ N
1 ≤ K ≤ R-L+1
Example:
Input:
7 (N)
2 1 5 4 3 6 8 (sequence A)
4 (Q)
1 2 2 (L R K)
3 7 4
4 6 2
5 5 1
Output:
2
6
4
3