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  ≤  10⁵) and Q (1 ≤ Q  ≤ 10⁵).

The next line contains N possibly distinct integers a_i ( -10⁹  ≤ a_i ≤ 10⁹).

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.