# K-th Number

## Description

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 file contains n — the size of the array, and m — the number of questions to answer (1 <= n <= 100 000, 1 <= m <= 5 000). The second line contains n different integer numbers not exceeding 109 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).

## Output

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

### Sample Input

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


### Sample Output

5
6
3


# Solution

## Code

//=============================================================
// File Name: poj-2104.cpp
// Author: Wycer
// Created Time: 2018-05-07 17:33
//=============================================================
#include <cstdio>
#include <algorithm>
const int N = 1e5 + 10;
using namespace std;
{
int x = 0, f = 1;
char ch = getchar();
while (ch < '0' || '9' < ch)
{
if (ch == '-')
f = -1;
ch = getchar();
}
while ('0' <= ch && ch <= '9')
{
x = x * 10 + ch - 48;
ch = getchar();
}
return x * f;
}
int n, m, a[N], tag[N], back[N], root[N];
{
for (int i = 1; i <= n; ++i)
{
tag[i] = i;
back[i] = a[i];
}
}

struct node
{
int l, r, cnt;
node()
{
l = r = cnt = 0;
}
} tr[20 * N];
int cnt = 0;
void insert(int &k, int l, int r, int x)
{
tr[++cnt] = tr[k];
k = cnt;
++tr[k].cnt;
if (l == r)
return;
int mid = (l + r) >> 1;
if (x <= mid)
insert(tr[k].l, l, mid, x);
else
insert(tr[k].r, mid + 1, r, x);
}
int query(int x, int y, int l, int r, int k)
{
if (l == r)
return l;
int tmp = tr[tr[y].l].cnt - tr[tr[x].l].cnt;
int mid = (l + r) >> 1;
if (k <= tmp)
return query(tr[x].l, tr[y].l, l, mid, k);
else
return query(tr[x].r, tr[y].r, mid + 1, r, k - tmp);
}
bool cmp(int x, int y)
{
return a[x] < a[y];
}
int r[N];
void solve()
{
sort(tag + 1, tag + n + 1, cmp);
for (int i = 1; i <= n; ++i)
r[tag[i]] = i;
for (int i = 1; i <= n; ++i)
{
root[i] = root[i - 1];
insert(root[i], 1, n, r[i]);
}

int x, y, k;
while (m--)
{
printf("%d\n", a[tag[query(root[x - 1], root[y], 1, n, k)]]);
}
}

int main()
{