#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 1e5 + 10;
/*
root[i]:表示第i个版本的根节点
*/
int root[N], a[N], idx;
int n, m;
struct node
{
//l 表示左儿子, r 表示右儿子, cnt表示该结构体区间含有几个数字
int l, r;
int cnt;
}tr[4 * N + N * 17];//4*N线段树要开4倍空间,17 * N: 表示N个操作 * 每次操作最多改变logN=17个节点
vector<int> nums;
int build(int l, int r)
{
int p = ++ idx;
if(l == r) return p;
int mid = l + r >> 1;
tr[p].l = build(l, mid);
tr[p].r = build(mid + 1, r);
return p;
}
//找到a[i]离散化后的值
int find(int x)
{
return lower_bound(nums.begin(), nums.end(), x) - nums.begin();
}
//p:上个版本; l: 区间左端点, r:区间右端点; x:要插入的数字
int insert(int p, int l, int r, int x)
{
//给新版本q分配一个新的节点
int q = ++idx;
//线段树的持久化,总节点数不变,改变的只是某个路上的信息,所以先将q完全继承p,再看x的位置来改变某个儿子信息
tr[q] = tr[p];
if(l == r)
{
tr[q].cnt++;
return q;
}
int mid = l + r >> 1;
//x在左边就去左边,给左边的新路分配新的节点
if(x <= mid) tr[q].l = insert(tr[p].l, l, mid, x);
//x在右边就去右边,给右边的新路分配新的节点
else tr[q].r = insert(tr[p].r, mid + 1, r, x);
//最后更新区间tr[q]的cnt = 左右两个儿子cnt的和
tr[q].cnt = tr[tr[q].l].cnt + tr[tr[q].r].cnt;
return q;
}
/*
p:之前的版本
q:现在的版本
l:区间左端点
r:区间右端点
k:第k小的数
*/
int query(int p, int q, int l, int r, int k)
{
//当l == r的时候说明我们已经找到这个数,直接返回这个点离散化后的值,即在vector里面的位置
if(l == r) return r;
//版本q左区间的数的个数 - 版本p左区间数的个数 = a[p+1] ~ a[q] 里面左区间的数的个数
int cnt = tr[tr[q].l].cnt - tr[tr[p].l].cnt;
int mid = l + r >> 1;
//k <= cnt表示第k个数一定在左区间里面
if(k <= cnt) return query(tr[p].l, tr[q].l, l, mid, k);
//否则就在右区间的第k-cnt个位置
else return query(tr[p].r, tr[q].r, mid + 1, r, k - cnt);
}
int main()
{
scanf("%d%d", &n, &m);
for(int i = 0; i < n; i++)
{
scanf("%d", &a[i]);
nums.push_back(a[i]);
}
//离散化
sort(nums.begin(), nums.end());
nums.erase(unique(nums.begin(), nums.end()), nums.end());
//先初始第一个版本也就是空数组的时候
root[0] = build(0, nums.size() - 1);
for(int i = 0; i < n; i++)
//每加入一个数就是一个版本,初始这个版本
root[i + 1] = insert(root[i], 0, nums.size() - 1, find(a[i]));
int l, r, k;
while(m --)
{
scanf("%d%d%d", &l, &r, &k);
//query返回第k小的数离散化后的值
printf("%d\n", nums[query(root[l - 1], root[r], 0, nums.size() - 1, k)]);
}
}