ILKQUERY  I LOVE KdTREES
You've been invited to the "ILoveKdtrees'' 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 kth smallest element until the index i (i.e. if the first i+1 elements were sorted in nondescending way, d would be the element at index k  1 ). Then, the answer to each query is the index of the lth 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 ≤ 10^{5}) and Q (1 ≤ Q ≤ 10^{5}).
The next line contains N possibly distinct integers a_{i} ( 10^{9} ≤ a_{i} ≤ 10^{9}).
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 it's 2nd ocurrency, so the answer is 6.
hide comments
randomguy00:
20160224 15:37:06


randomguy00:
20160224 15:36:29
how to do better than O(q*n)? getting tle with it!!!


farhan764:
20160222 19:21:51
would u plz check my submission .....what is the problem with it 

[Rampage] Blue.Mary:
20160217 05:01:59
(1) What does 0th smallest element mean?


bsubercaseaux:
20160216 22:22:50
Q set up to 10^5 ! 

[Rampage] Blue.Mary:
20160216 17:35:39
Q can be set up to at least 10^5. 10^3 is a somewhat low constraint. 
Added by:  BerSub 
Date:  20160212 
Time limit:  0.400s1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 GOSU JSMONKEY 
Resource:  My own 