## 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 62 6 7 1 8 1 2 3 2 62 4 22 6 31 4 11 4 23 4 23 3 2
Output:
6-13599Explanation 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.```