主席树 又称函数式线段树，又称可持久化线段树……缺点是内存有点儿大……
type node1=record
l,r,sum:longint;
end;
node2=record
x,idx:longint;
end;
var q,i,j,k,tot,n,m:longint;
a:array[..] of node2;
rank,root:array[..] of longint;
t:array[..] of node1;
procedure qsort(h,l:longint);
var i,j,m:longint;
temp:node2;
begin
i:=h;j:=l;m:=a[(i+j)>>].x;
repeat
while a[i].x<m do inc(i);
while a[j].x>m do dec(j);
if i<=j then
begin
temp:=a[i];a[i]:=a[j];a[j]:=temp;
inc(i);dec(j);
end;
until i>j;
if i<l then qsort(i,l);
if j>h then qsort(h,j);
end;
procedure insert(var x:longint;num,l,r:longint);
var mid:longint;
begin
t[tot]:=t[x];
x:=tot;
inc(tot);
inc(t[x].sum);
if l=r then exit;
mid:=(l+r)>>;
if num<=mid then insert(t[x].l,num,l,mid)
else insert(t[x].r,num,mid+,r);
end;
function query(i,j,k,l,r:longint):longint;
var mid,tmp:longint;
begin
if l=r then exit(l);
tmp:=t[t[j].l].sum-t[t[i].l].sum;
mid:=(l+r)>>;
if k<=tmp then exit(query(t[i].l,t[j].l,k,l,mid))
else exit(query(t[i].r,t[j].r,k-tmp,mid+,r));
end;
procedure main;
begin
t[].l:=;t[].r:=;t[].sum:=;root[]:=;
readln(n,m);
for i:= to n do begin read(a[i].x);a[i].idx:=i;end;
qsort(,n);
tot:=;
for i:= to n do rank[a[i].idx]:=i;
for i:= to n do
begin
root[i]:=root[i-];
insert(root[i],rank[i],,n);
end;
for q:= to m do
begin
readln(i,j,k);
writeln(a[query(root[i-],root[j],k,,n)].x);
end;
end;
begin
main;
end.