#include<bits/stdc++.h>
#define int long long
#define cs const
#define il inline
#define ri register
#define pc(i) putchar(i)
using namespace std;
il void read(int &as)
{
    as=0;int f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') as=(as<<3)+(as<<1)+(ch^48),ch=getchar();as*=f;
}
void wt(int x){if(x<0)x=-x,pc('-');if(x>9) wt(x/10);pc(x%10|48);}
cs int N=1e6+7;
int ro[N*31],sum[N*31],ls[N*31],rs[N*31],tot,n,m,val[N];
#define mid (l+r>>1)
void build(int &cur,cs int l,cs int r)
{
    cur=++tot; 
    if(l==r) return sum[tot]=val[l],void();
    build(ls[cur],l,mid),build(rs[cur],mid+1,r);
}
void ins(int &cur,cs int pre,cs int l,cs int r,cs int q,cs int k)
{
    cur=++tot;
    ls[cur]=ls[pre],rs[cur]=rs[pre],sum[cur]=sum[pre];
    if(l==r) return sum[cur]=k,void();
    if(q<=mid) ins(ls[cur],ls[pre],l,mid,q,k);
    if(q>mid) ins(rs[cur],rs[pre],mid+1,r,q,k);
}
int query(cs int cur,cs int l,cs int r,cs int q)
{
    if(l==r) return sum[cur];
    if(q<=mid) return query(ls[cur],l,mid,q);
    if(q>mid) return query(rs[cur],mid+1,r,q);
}
signed main()
{
    read(n),read(m);
    for(ri int i=1;i<=n;++i) read(val[i]);
    build(ro[0],1,n);
    for(ri int i=1,op,x,y,cur;i<=m;++i)
    {
        read(cur),read(op);
        if(op==1) read(x),read(y),ins(ro[i],ro[cur],1,n,x,y);
        else read(x),wt(query(ro[cur],1,n,x)),pc('\n'),ro[i]=ro[cur];
    }
    return 0;
}

#include<bits/stdc++.h>
#define cs const
#define il inline
#define ri register
#define pc(i) putchar(i)
using namespace std;
il void read(int &as)
{
    as=0;int f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') as=(as<<3)+(as<<1)+(ch^48),ch=getchar();as*=f;
}
void wt(int x){if(x<0)x=-x,pc('-');if(x>9) wt(x/10);pc(x%10|48);}
cs int N=2e5+7;
int A[N],lsh[N],tot,ro[N],n,m,Lsh;
struct Seg{int ls,rs,v;}t[N<<5];
#define mid (l+r>>1)
void build(int &cur,cs int l,cs int r)
{
    cur=++tot; if(l==r) return;
    build(t[tot].ls,l,mid),build(t[tot].rs,mid+1,r);
}
void add(int &cur,cs int pre,cs int l,cs int r,cs int pos)
{
    cur=++tot,t[cur]=t[pre],t[cur].v++;
    if(l==r) return;
    if(pos<=mid) add(t[cur].ls,t[cur].ls,l,mid,pos);
    else add(t[cur].rs,t[pre].rs,mid+1,r,pos);
}
int query(cs int nl,cs int nr,cs int l,cs int r,cs int k)
{
    if(l==r) return lsh[l];
    int x=t[t[nr].ls].v-t[t[nl].ls].v;
    if(x>=k) return query(t[nl].ls,t[nr].ls,l,mid,k);
    else return query(t[nl].rs,t[nr].rs,mid+1,r,k-x);
}
signed main()
{
    read(n),read(m);
    for(ri int i=1;i<=n;++i) read(A[i]),lsh[i]=A[i];
    sort(lsh+1,lsh+1+n),Lsh=unique(lsh+1,lsh+1+n)-lsh-1;
    build(ro[0],1,Lsh);
    for(ri int i=1,x;i<=n;++i)
        x=lower_bound(lsh+1,lsh+1+Lsh,A[i])-lsh,
        add(ro[i],ro[i-1],1,Lsh,x);
    for(ri int i=1,l,r,k;i<=m;++i)
        read(l),read(r),read(k),wt(query(ro[l-1],ro[r],1,Lsh,k)),pc('\n');
    return 0;
}