/*
划分树，求解给定区间[l, r]的第k小。
和归并是相反，相当于把归并树倒过来。
当访问到节点t时，sum[bit][i](left <= i <= right)表示从第left个数到第i个数中
有sum[bit][i]个数进入了左子树。
假如我们在区间[left, right]中求解[l, r]中的第k小的时候(left <= l <= r <= right)，
看在区间[l,r]中有多少个数进入了左子树，如果有s个，如果s>=k,则递归到左节点，但是
要注意的是，当访问的左节点的时候，求解的区间[l, r]要发生变化 ,即找到区间[l, r]中
第一次出现在左子树的位置ll，和最后一次出现在左子树的位置rr,然后访问左子树的区间
[ll, rr]，一直到left=right，返回元数列sa[left]为所求。
*/
#include <iostream>
#include <algorithm>
using namespace std;
#define MAX_SIZE 100010
struct Tree
{
int l, r, bit;
}tree[3 * MAX_SIZE];
int sum[24][MAX_SIZE]; //记录划分过程的数组，需要空间为n*logn
int a[2][MAX_SIZE]; // 滚动数组， 在划分过程中，保存上一层的序列,最开始时将
//将数组存放到a[0][i]中
int sa[MAX_SIZE]; // 排序数组
void MakeTree(int k, int bit, int l, int r)
{
tree[k].bit = bit;
tree[k].l = l, tree[k].r = r;
if (l == r)
return ;
int inf = (bit & 1);
int low = (l + r) >> 1;
int temp = 0;
int t = 0;
int c = 0;
while (low - temp >= l && sa[low - temp] == sa[low])temp++;
int i = l, j = low + 1;
for (;l <= r; l++)
{
if (a[inf][l] < sa[low])
{
c++;
sum[bit][l] = c;
a[1 - inf][i++] = a[inf][l];
}
else if (a[inf][l] == sa[low] && t < temp)
{
c++;
sum[bit][l] = c;
a[1 - inf][i++] = a[inf][l];
t++;
}
else
{
sum[bit][l] = c;
a[1 - inf][j++] = a[inf][l];
}
}
l = tree[k].l;
MakeTree(2 * k, bit + 1, l, low);
MakeTree(2 * k + 1, bit + 1, low + 1, r);
}
int Find_rank(int k, int l, int r, int t)
{
int bit = tree[k].bit;
int left = tree[k].l, right = tree[k].r;
int low = (left + right) >> 1;
if (right == left)
{
return sa[left];
}
int s;
if (l == left)
s = sum[bit][r];
else
s = sum[bit][r] - sum[bit][l - 1];
if (s >= t)
{
if (l == left)
return Find_rank(2 * k, left, left + sum[bit][r] - 1, t);
else
return Find_rank(2 * k, left + sum[bit][l - 1], left + sum[bit][r] - 1, t);
}
else
{
if (l == left)
return Find_rank(2 * k + 1, low + 1, low + 1 + r - l - s, t - s);
else
return Find_rank(2 * k + 1, low + 1 + l - left - sum[bit][l - 1], low + r - left + 1 - sum[bit][r], t - s);
}
}
int main()
{
int i, j, k, l, m, n, t, r;
while (scanf("%d%d", &n, &m) != EOF)
{
memset(sum, 0, sizeof(sum));
for (i = 1; i <= n; i++)
{
scanf("%d", &a[0][i]);
sa[i] = a[0][i];
}
sort(sa + 1, sa + n + 1);
MakeTree(1, 0, 1, n);
for (i = 0; i < m; i++)
{
scanf("%d%d%d", &l, &r, &k);
printf("%d\n", Find_rank(1, l, r, k));
}
}
return 0;
}