ILKQUERY - I LOVE Kd-TREES

no tags 

You've been invited to the "I-Love-Kd-trees" annual con, but first, you have to show them that you really know about great data structures, so they give you an easy task!

You are given a list of N numbers and Q queries, each query consist of three integers: k, i and l; let d be the k-th smallest element until the index i (i.e. if the first i+1 elements were sorted in non-descending way, d would be the element at index k - 1). Then, the answer to each query is the index of the l-th occurrence of d in the array. If there's no such index, the answer is -1. You have to consider that all indexes are counted starting with 0.

Input

Input consists of one test case.

The first line contains two integers, N (1 ≤ N ≤ 105) and Q (1 ≤ Q ≤ 105).

The next line contains N possibly distinct integers ai (-109 ≤ ai ≤ 109).

Then Q lines follow, each of those contains three integers k, i and l. (0 < k ≤ i < N, 1 ≤ l ≤ N).

Output

For each query (in the same order as the input) output a single line with the answer to that query.

Example

Input:

10 6
2 6 7 1 8 1 2 3 2 6
2 4 2
2 6 3
1 4 1
1 4 2
3 4 2
3 3 2
Output: 6
-1
3
5
9
9

Explanation of the first query:

The elements until index 4 are [2,6,7,1,8] so the 2nd smallest element is 2, and your asked for the index of its 2nd occurrence, so the answer is 6.


hide comments
randomguy00: 2016-02-24 15:36:29

how to do better than O(q*n)? getting tle with it!!!

farhan764: 2016-02-22 19:21:51

would u plz check my submission .....what is the problem with it

[Rampage] Blue.Mary: 2016-02-17 05:01:59

(1) What does 0-th smallest element mean?
(2) When dealing with elements, Multiply occurrence of the same number counted once or multiple times? e.g. The 3rd smallest element of [1,1,2,3] is 2 or 3?

Edit: my AC program assumes the following:
(1)If i=n => i=n-1
(2)If k=0 => res=-1

Last edit: 2016-02-17 05:10:00
bsubercaseaux: 2016-02-16 22:22:50

Q set up to 10^5 !

[Rampage] Blue.Mary: 2016-02-16 17:35:39

Q can be set up to at least 10^5. 10^3 is a somewhat low constraint.


Added by:BerSub
Date:2016-02-12
Time limit:0.400s-1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY
Resource:My own