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