#include <bits/stdc++.h>
using namespace std;
#define int long long

const int N=2e5+5;
struct node
{
    int val;
    //gl,gr分别存储左右子节点的位置
    int gl;
    int gr;
}seg[N<<6];
struct Node
{
    int val;
    int pos;
};
int n,m,in;
int l,r,k;
int cnt;
int root[N];//存储每棵树的根节点
int g[N];//存储每个数离散化后的排名

vector<Node>all;

inline bool it(Node m1,Node m2)
{
    return m1.val<m2.val;
}

void init()//离散化处理
{
    for(int i=1;i<=n;i++)
    {
        cin>>in;
        all.push_back({in,i});
    }
    sort(all.begin(),all.end(),it);
    g[all[0].pos]=1;
    for(int i=1,_count=1;i<n;i++)
    {
        if(all[i].val!=all[i-1].val)_count++;
        g[all[i].pos]=_count;
    }
}

inline void Modify(int old,int pos,int L,int R)//old为上一棵线段树的对应节点位置
{
    int newpos=++cnt;seg[newpos]=seg[old];//newpos是目前正在建立的节点
    seg[newpos].val++;
    if(L==R)return;

    int mid=L+R>>1;
    if(pos<=mid)
    {
        seg[newpos].gl=cnt+1;
        Modify(seg[old].gl,pos,L,mid);
    }
    else
    {
        seg[newpos].gr=cnt+1;
        Modify(seg[old].gr,pos,mid+1,R);
    }
}

inline int Query(int lpos,int rpos,int L,int R,int c)
{
    if(L==R)return L;

    int mid=L+R>>1;
    //同时查询l-1和r两棵线段树
    int tmp=seg[seg[rpos].gl].val-seg[seg[lpos].gl].val;//左子树差值
    if(tmp>=c)return Query(seg[lpos].gl,seg[rpos].gl,L,mid,c);
    else return Query(seg[lpos].gr,seg[rpos].gr,mid+1,R,c-tmp);
}

signed main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n>>m;
    init();
    for(int i=1;i<=n;i++)
    {
        root[i]=cnt+1;
        Modify(root[i-1],g[i],1,n);
    }
    while(m--)
    {
        cin>>l>>r>>k;
        cout<<all[Query(root[l-1],root[r],1,n,k)-1].val<<'\n';
    }
    return 0;
}

错误样例： 1000 1 8431 24786 27989 24315 4460 15644 9589 19680 3375 24768 16385 3606 13117 23745 32702 14556 25903 24418 8372 1199 31192 11323 16362 8966 808 23181 28785 4160 11088 19923 8611 28891 27943 7321 15021 20198 11213 22929 3915 19385 28046 29412 4563 6627 15881 7110 26229 21348 31633 29773 15297 29 5075 25475 3177 24708 29625 22458 11849 20636 11919 24863 21156 22309 8293 23186 23473 13583 4020 5301 11094 2357 4676 14147 20275 23624 14668 19620 11746 10505 18652 11198 6525 13500 32376 13325 27489 19417 11013 4086 3378 14084 9194 29016 4896 31807 20335 31845 19304 16479 20584 21680 26397 23740 5400 134 8232 32045 19792 5762 142 23092 3031 26972 12017 25461 5902 9730 25690 28269 11476 6122 28469 15712 15784 1958 26525 29331 25357 26553 30938 17340 5427 17321 25640 439 25555 9557 8378 18554 13915 25737 15615 27467 22347 5328 25892 28977 20191 1417 13018 13736 20718 2109 10841 408 16914 28976 2213 12424 6153 1590 18192 13839 6491 20424 30720 6028 16445 87 24818 11799 17590 26080 30143 17592 4608 6593 6430 26326 11057 25291 18027 29426 17179 32152 2215 17813 2928 16159 25279 4230 32554 17797 3345 12865 11305 11063 11308 8613 16414 28725 25815 16877 23721 3505 29014 13025 30398 26584 7144 29005 17741 4592 17044 23475 802 6307 18469 28477 2058 18074 5748 20725 32055 5966 5605 30520 12517 19483 15924 1896 19774 22423 9330 15330 30331 4897 10826 26160 5197 29373 12937 24959 19067 11039 32478 2387 25804 32261 6877 2169 14887 8394 30794 5182 19193 28984 8341 26590 7895 27807 8097 5183 9573 7459 3017 30687 7798 29018 20261 29451 19828 12823 5641 11347 31747 2688 1743 31034 4065 22119 9943 16178 14352 10967 4299 24775 30008 19692 24616 2842 327 2792 30202 30609 23130 11140 31463 30157 29920 26500 17006 20956 22780 8590 29553 27312 12076 20540 6641 3280 41 20080 1562 25934 11278 1512 7295 8441 23739 10258 31654 3027 30588 26913 6855 17606 20966 29024 17873 22930 11778 30918 6830 24330 16814 16587 27592 22912 19775 24699 11212 2430 1387 5833 18094 28855 21607 5925 3053 9020 13900 1105 3608 14579 13503 3440 7057 29510 17873 24928 13457 27416 4644 27721 8812 23293 26192 4982 5142 22954 21380 25444 25574 6314 17265 25625 27291 31571 867 1975 925 6649 2737 26449 9861 1377 88 16893 14814 24184 17379 29227 813 5701 32142 19765 22576 27165 31146 8503 30052 28694 21315 17696 7625 18366 12801 28425 26601 17164 8012 17606 23575 7062 14003 23227 18421 2053 13711 5361 27449 17862 11747 7786 25008 27395 24711 27313 28291 5330 646 30132 3257 17836 29124 13782 26877 2080 7396 29761 10401 10696 8808 32633 8676 8829 27418 27703 26992 31687 17323 22644 22823 19607 14747 25796 29727 7481 16216 22501 19435 18308 23466 8344 19229 10068 26702 10671 2312 12090 9186 13416 2763 13681 6913 11513 5515 3348 11438 11628 30207 16271 11766 8877 24882 31316 28881 18402 21124 1231 12874 27642 2802 21147 13279 13705 5528 1526 1067 22739 30068 30322 15042 29734 24685 4078 11101 1646 11156 7621 21559 13315 19625 22085 2998 19909 5345 14947 12622 20075 2278 7596 26019 16920 31264 27263 3565 19503 17715 30330 9889 16233 22985 31538 10574 31781 28561 1831 2500 2303 3208 31479 3708 6563 16503 26321 2100 30692 14780 23597 11482 776 5966 1978 6571 14694 7164 10136 16540 52 9973 12744 17657 7578 5517 16097 2892 6410 29246 3332 128 30164 5357 12049 23622 31733 6255 15387 25272 816 18764 4890 26940 29793 29123 1760 8876 29965 9998 1615 30388 28989 31719 5320 26747 30605 15434 9958 20613 7040 5757 14189 28120 21014 21838 10365 4701 31905 3996 17676 28298 5588 28952 30355 16446 13597 77 774 26860 23605 1502 26378 12028 17141 30991 8291 11886 5483 5511 31915 15553 22573 32341 16458 17427 26349 4656 14754 22921 16718 21763 5258 4849 6646 4777 510 24486 23524 7924 2068 26804 6660 22261 3634 15421 7425 18295 31103 18460 859 7373 28055 26567 10169 16334 1411 2426 16768 17437 6376 11922 29604 2990 24958 19255 15807 17285 5316 18749 864 7617 17907 12876 7589 27866 9264 17727 11020 1063 26885 31435 4486 419 2834 15713 26317 25840 2304 22613 13048 6044 24759 25151 16717 19108 1745 9890 29526 19766 29262 21195 18999 16571 4233 27132 6718 19989 13674 17610 7356 16421 23518 8132 21523 10129 19076 32085 30225 27588 28842 24300 20604 27958 3959 6489 23534 7405 873 18555 28899 11588 16899 9752 21265 16363 24511 18444 1784 13615 12874 2470 9657 123 25328 9295 9003 9759 1365 15212 14892 18001 1639 24454 29493 22897 1936 19624 31026 402 31280 26633 12432 5429 3914 16619 17559 18263 20350 6339 7930 4271 28471 13978 32172 15921 13093 2483 6902 18646 30958 24430 7111 23199 14368 12396 14411 9432 3947 18676 21182 27546 12813 20630 28803 27283 18829 29966 18800 30473 8108 15467 24941 797 9369 17008 24637 26189 9572 25914 7067 3901 18101 9507 1929 695 6078 15335 229 19440 20846 12037 9789 16909 5607 24936 13028 18149 17459 26695 4165 25353 13362 10058 4472 25346 28375 30702 3347 23001 13972 24618 18755 11485 29715 7251 28187 3232 23335 61 29227 32579 23554 29603 13653 24563 13480 3528 15836 30644 13988 5215 19390 4957 5369 25000 13892 15076 20059 30173 18391 28124 1951 14284 3093 2364 27249 10437 17444 14946 23621 4022 30022 9048 8592 24469 17838 5205 16695 23806 7059 32391 15431 18206 12930 1039 28136 1999 6904 18766 10124 12036 22576 27487 23916 15720 4154 16356 30517 578 589 16902 6398 4252 14174 20663 30846 4004 8433 8762 4732 27218 6704 4326 21638 8779 32570 9511 3814 18950 20157 197 17106 27181 2503 3945 8419 22086 17881 8285 19401 13458 9534 19859 13116 15669 10650 21481 6965 29848 5318 16555 9055 25868 19419 6233 25288 7088 28813 23211 27613 27796 9403 2003 19605 16926 11331 2818 24300 31661 24859 11821 32147 8061 11678 31505 28902 25547 291 11637 10270 21305 29396 6831 4808 4211 1726 12905 11894 20 824 515 期望输出：20275