Contests | Virtual Contests | Problems | Submit | Runs Status | Rank List | Forum |

Time Limit: 10.0 Seconds Memory Limit: 65536K

Total Runs: 1299 Accepted Runs: 364 Multiple test files

Case Time Limit: 2.0 Seconds

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.
### Input

### Output

### Sample Input

### Sample Output

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.

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*).

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

7 3 1 5 2 6 3 7 4 2 5 3 4 4 1 1 7 3

5 6 3

Maintance:Fxz. Developer: SuperHacker, G.D.Retop, Fxz