96pts，一直 T 第 6 个点，有没有好心人帮忙卡一卡qwq

#include<iostream>
#include<vector>
#include<cstring>
#include<algorithm>
#define file_in(x) (freopen(#x".in","r",stdin))
#define file_out(x) (freopen(#x".out","w",stdout))
using namespace std;
const int N=1e5+5;

template<class type> type read(type ret=0,int w=0,char ch=getchar()){
    while(!isdigit(ch)) w=ch=='-',ch=getchar();
    while(isdigit(ch)) ret=ret*10+ch-'0',ch=getchar();
    return w?-ret:ret;
}
template<class type> void _write(type x){
    if(x<0) return putchar('-'),_write(-x);
    if(x>9) _write(x/10);
    putchar('0'+x%10);
}
template<class type> void write(type x){_write(x),putchar('\n');}
		
int n,m,a[N],cnt[N],tmp[N],refl[N],fa[N],siz[N],cntedg,head[N],rp[N],lp[N],bel[N],pos[N],bsiz,stksiz,ans[N],tot;
struct query{int u,k,id;};
struct edge{int to,nxt;}edg[N];
vector<query> qry[N];
struct{int u,v,w;}stk[N];
struct{int u,v;}val[N];

void add(int u,int v){edg[++cntedg]={v,head[u]},head[u]=cntedg;}

int find(int u){return fa[u]==u?u:find(fa[u]);}

bool merge(int u,int v){
    u=find(u),v=find(v);
    if(u==v) return 0;
    if(siz[u]>siz[v]) swap(u,v);    
    fa[u]=v,siz[v]+=siz[u],stk[++stksiz]={u,v,siz[u]};
    return 1;
}

void back(){
    int u=stk[stksiz].u,v=stk[stksiz].v,w=stk[stksiz].w;
    fa[u]=u,siz[u]=w,siz[v]-=w,--stksiz;
}

void dfs(int u,int w){
    static int aff[N];     
    if(u!=1) aff[u]=merge(val[u].u,val[u].v);
    for(auto &i:qry[u]){
        if(i.k<=0) continue;	
        int rt=find(i.u);
        if(i.k>siz[rt]) i.k-=siz[rt];
        else
            for(int j=lp[w];j<=rp[w];++j)
            if(find(refl[j])==rt)
                if(--i.k==0){ans[i.id]=tmp[j];break;}
        }    
    for(int i=head[u];i;i=edg[i].nxt) dfs(edg[i].to,w);
    if(aff[u]) back();
}

void discrt(){
    memcpy(tmp,a,sizeof(a)),sort(tmp+1,tmp+1+n);
    for(int i=1;i<=n;++i) a[i]=lower_bound(tmp+1,tmp+1+n,a[i])-tmp;
    for(int i=1;i<=n;++i) a[i]+=cnt[a[i]]++,refl[a[i]]=i;
}

signed main(){
    n=read<int>(),m=read<int>(),bsiz=4500;
    for(int i=1;i<=n;++i) a[i]=read<int>();
    discrt(),pos[0]=1;
    for(int i=1,cur=1;i<=m;++i){
        int opt=read<int>();
        if(opt==1) add(cur,i+1),val[i+1]={read<int>(),read<int>()},cur=i+1;
        else if(opt==2) cur=pos[read<int>()];
        else qry[cur].push_back({read<int>(),read<int>(),++tot});
        pos[i]=cur;
    }
    for(int i=1;i<=n;++i){
        bel[i]=i/bsiz+1;
        if(bel[i]!=bel[i-1]) lp[bel[i]]=i,rp[bel[i]-1]=i-1;
    }
    memset(ans,-1,sizeof(ans));
    rp[bel[n]]=n,lp[bel[n]+1]=n+1;
    for(int i=1;i<=bel[n];++i){
        for(int j=1;j<=n;++j) fa[j]=j,siz[j]=a[j]>=lp[i]&&a[j]<=rp[i];
        dfs(1,i);
    }
    for(int i=1;i<=tot;++i) write(ans[i]);
    return 0;
}

//~kawaii~