## MKTHNUM - K-th Number

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

### Output

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

### Example

```Input:
7 3
1 5 2 6 3 7 4
2 5 3
4 4 1
1 7 3

Output:
5
6
3```

## Code Examples

### #1 Code Example with C++ Programming

```Code - C++ Programming```

``````#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

#define MOD                 1000000007LL
#define EPS                 1e-9
#define io                  ios_base::sync_with_stdio(false);cin.tie(NULL);
#define M_PI                3.14159265358979323846

const int MAXN = 1e5+5;

int n, m;
vector<int> tree[4*MAXN];
vector<pair<int, int> > table;
int arr[MAXN];

void build(int node, int start,  int end){
if(start > end)		return;

if(start==end){
tree[node].push_back(table[start].second);
return;
}
int mid = (start + end) >> 1;
int left = node << 1, right = left + 1;
build(left, start, mid);
build(right, mid + 1, end);
merge(tree[left].begin(), tree[left].end(), tree[right].begin(), tree[right].end(), back_inserter(tree[node]));
}

int query(int node, int start, int end, int l, int r, int k){
if(start == end)
return tree[node][0];
int mid = (start + end) >> 1;
int left = node << 1, right = left + 1;
auto it = upper_bound(tree[left].begin(), tree[left].end(), r);
int total = it - lower_bound(tree[left].begin(), tree[left].end(), l);
if(total >= k){
return query(left, start, mid, l, r, k);
}else{
return query(right, mid + 1, end, l, r, k - total);
}
}

int main(){
io;
cin >> n >> m;
for(int i = 0; i < n; i++){
int x;
cin >> x;
arr[i] = x;
table.push_back({x, i});
}
sort(table.begin(), table.end());
build(1, 0, n - 1);
for(int i = 0; i < m; i++){
int l, r, k;
cin >> l >> r >> k;
--l, --r;
int idx = query(1, 0, n - 1, l, r, k);
cout << arr[idx] << endl;
}
return 0;
}``````
Copy The Code &

Input

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

Output

cmd
5
6
3