## 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!!!

 < Previous 1 2 3 4 5 6 7 Next > Shahed Shahriar: 2015-09-26 04:15:28 in c++(g++4.3.2) got WA and with the same code got AC in c++14 (g++5.1) Pulkit Singhal: 2015-09-01 08:52:34 Persistent Segment Tree Nailed It :D anando_du: 2015-07-22 12:05:51 used scanf() printf() got AC .. used getchar_unlocked() , putchar_unlocked() got wa O.o btw nice one ! ankit kumar: 2015-07-03 16:29:21 !micro !soft=macro hard; hahaha nyc.. problem indeed!! i_am_looser: 2015-06-10 16:56:38 persistent segment tree. Got AC using O(nlog(n)) ; ) gyosh: 2014-01-19 15:09:58 Beautiful problem. There exists solution which run in O(log^3 N), O(log^2 N), and O(log N) per query. Explore them and learn something new! not as beautiful as you Last edit: 2015-04-03 01:00:56