## MKTHNUM - K-th Number

 English Vietnamese

You are working for Macrohard company in data structures department. After failing your previous task about key insertion you were asked to write a new data structure that would be able to return quickly k-th order statistics in the array segment.

That is, given an array a[1 ... n] of different integer numbers, your program must answer a series of questions Q(i, j, k) in the form: "What would be the k-th number in a[i ... j] segment, if this segment was sorted?"

For example, consider the array a = (1, 5, 2, 6, 3, 7, 4). Let the question be Q(2, 5, 3). The segment a[2 ... 5] is (5, 2, 6, 3). If we sort this segment, we get (2, 3, 5, 6), the third number is 5, and therefore the answer to the question is 5.

### Input

The first line of the input contains n — the size of the array, and m — the number of questions to answer (1 ≤ n ≤ 100000, 1 ≤ m ≤ 5000).

The second line contains n different integer numbers not exceeding 10^9 by their absolute values — the array for which the answers should be given.

The following m lines contain question descriptions, each description consists of three numbers: i, j, and k (1 ≤ i ≤ j ≤ n, 1 ≤ k ≤ j - i + 1) and represents the question Q(i, j, k).

```SAMPLE INPUT
7 3
1 5 2 6 3 7 4
2 5 3
4 4 1
1 7 3

```

### Output

```
For each question output the answer to it — the k-th number in sorted
a[i ... j] segment.

SAMPLE OUTPUT
5
6
3
```
Note : naive solution will not work!!! crazymax: 2016-10-31 15:01:26 Mo+ordered_set_tree (complexity with - Q*sqrt(N)*log(N)+N*sqrt(N)) solution gives TLE. :( Ravi kumar: 2016-10-25 15:57:06 Increase time limit for java. there is not even a single accepted solution. using (n+m)*logn complexity algo. Edit: i tried the same algo in C++ and it passed. you need to increase time limit for java. Last edit: 2016-10-25 16:17:58 i_m_a_coder: 2016-09-07 22:35:48 i did it using vectors and iterators bt getting wrong answer!!! tamionv: 2016-08-27 03:56:22 I think I'm the first one to solve it in O((N+Q) * sqrt(N)) :) kiwi1995: 2016-07-21 08:08:37 learnt a lot from this problem...:D akshayv3: 2016-07-16 11:01:50 Solved using Persistent Segment trees and execution time was 0.5 s and the same solution times out in c++ 4.3.2 shiva_swag1: 2016-06-24 21:10:51 binary search +persistence segment tree.. binary search over -10^9 to +10^9 got tle.. binary search over elements of arr got ac.. log(2*10^9) factor proved very costly than log(10^5)... :-) oleg007: 2016-01-01 19:01:50 @anando_du same thing happened to me , your comment was helpful Abhinandan Agarwal: 2015-10-18 20:39:53 N(log N)+M(log N)**3 solution gives TLE .. :-\ Sudharsansai: 2015-09-29 19:14:58 Learnt a lot . Merge Sort Tree : O((N+M)*lgN*lgN) Persistent Segment Tree : O((N+M)*lgN)