ILKQUERY - I LOVE Kd-TREES
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?
|
|
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 |