28 pts

#pragma GCC optimize(3)
#pragma GCC optimize(Ofast)
#include<cstdio>
#define N 100005
#define NN 135
#define _ 800
int n,m,a[N],va[N],p[N],cnt[N],cnt2[NN];
struct kuai{
	int v[NN],va[N],vc[NN],vac[N];
	int r[N]; 
}k[NN];
inline void reco(){
	for(int i=0;i<NN;i++)k[0].vc[i]=k[0].v[i];
	for(int i=0;i<N;i++)k[0].vac[i]=k[0].va[i];
	for(int i=1;i<NN;i++){
		for(int j=0;j<NN;j++)k[i].vc[j]=k[i-1].vc[j]+k[i].v[j];
		for(int j=0;j<N;j++)k[i].vac[j]=k[i-1].vac[j]+k[i].va[j];
	}
}
inline void recoo(int x,int y){
	k[0].vc[x/_]=k[0].v[x/_];
	k[0].vc[y/_]=k[0].v[y/_];
	k[0].vac[x]=k[0].va[x];
	k[0].vac[y]=k[0].va[y];
	for(int i=1;i<NN;i++){
		k[i].vc[x/_]=k[i].v[x/_]+k[i-1].vc[x/_];
		k[i].vc[y/_]=k[i].v[y/_]+k[i-1].vc[y/_];
		k[i].vac[x]=k[i].va[x]+k[i-1].vac[x];
		k[i].vac[y]=k[i].va[y]+k[i-1].vac[y];
	}
}
int qu(int now){
	if(p[now]!=now)p[now]=qu(p[now]);
	return p[now];
}
bool bb[100005],b2[100005];
inline void rebuild(int id,int x,int y,int l,int r){//printf("(%d %d %d)",id,l,r);
	if(l>r)return;
	k[id].v[x/_]-=k[id].va[x];
	k[id].va[x]=k[id].r[x]=0;
	for(int i=id*_;i<(id+1)*_&&i<=n;i++){
		if(va[qu(i)]==x&&i>=l&&i<=r)bb[i]=1;
		else if(va[qu(i)]==x)b2[i]=1;
	}
	for(int i=id*_;i<(id+1)*_&&i<=n;i++){
		if(bb[i]){
			if(!k[id].r[y])k[id].r[y]=i,va[i]=y;
			p[i]=k[id].r[y];
			k[id].v[y/_]++;
			k[id].va[y]++;
			bb[i]=0;
		}
		else if(b2[i]){
			if(!k[id].r[x])k[id].r[x]=i,va[i]=x;
			p[i]=k[id].r[x];
			k[id].v[x/_]++;
			k[id].va[x]++;
			b2[i]=0;
		}
	}
}
inline void read(int &a)
{
	a=0;char c;
	while((c=getchar())<48);
	do a=(a<<3)+(a<<1)+(c^48);
	while((c=getchar())>47);
}
inline void write(int x)
{
    if(x<0)putchar('-'),x=-x;
    if(x>9)write(x/10);
    putchar(x%10+'0');
}
inline void gor(int ll,int rr,int x,int y){
	for(int i=ll;i<=rr;i++){
		if(k[i].r[y])p[k[i].r[x]]=k[i].r[y];
		else k[i].r[y]=k[i].r[x],va[k[i].r[y]]=y;
		k[i].r[x]=0;
		int tt=k[i].va[x];
		k[i].v[x/_]-=tt;
		k[i].va[x]-=tt;
		k[i].v[y/_]+=tt;
		k[i].va[y]+=tt;
	}
}
int main(){
//	freopen("in.txt","r",stdin);
//	freopen("1.out","w",stdout);
	read(n),read(m);
	for(int i=1;i<=n;i++){
		read(a[i]);
		int nowk=i/_,kn=a[i]/_;
		k[nowk].va[a[i]]++;
		k[nowk].v[kn]++;
		if(!k[nowk].r[a[i]]) k[nowk].r[a[i]]=i,va[i]=a[i];
		p[i]=k[nowk].r[a[i]];
	}
	reco();
	while(m--){
		int op,l,r,K,x,y;
		read(op),read(l),read(r);
		if(op==2){
			read(K);
			bool b=0;
			int ll=-1,rr=-1;
			for(int i=l;i<=r;i++){
				if(i%_==0){
					ll=i/_;
					break;
				}
				//printf("^%d",va[qu(i)]);
				cnt[va[qu(i)]]++,cnt2[va[qu(i)]/_]++;
				if(i==r)b=1;
			}
			if(!b)for(int i=r;i>=l;i--){
				if((i+1)%_==0){
					rr=i/_;
					break;
				} 
				cnt[va[qu(i)]]++,cnt2[va[qu(i)]/_]++;
			}
			if((ll==-1||rr==-1)||ll>rr){
				int dd=0,sum=0;
				for(int i=0;i<NN;i++){
					if(sum+cnt2[i]>=K)break;
					sum+=cnt2[i];dd+=_;
				}
				for(;;dd++){
					if(sum+cnt[dd]>=K){
						write(dd);
						break;
					}
					sum+=cnt[dd];
				}
			}
			else{
				int dd=0,sum=0;
				for(int i=0;i<NN;i++){
					if(sum+cnt2[i]+k[rr].vc[i]-k[ll-1].vc[i]>=K)break;
					sum+=cnt2[i]+k[rr].vc[i]-k[ll-1].vc[i];dd+=_;
				}
				for(;dd<N;dd++){
					if(sum+cnt[dd]+k[rr].vac[dd]-k[ll-1].vac[dd]>=K){
						write(dd);
						break;
					}
					sum+=cnt[dd]+k[rr].vac[dd]-k[ll-1].vac[dd];
				}
			}
			for(int i=l;i<=r;i++){
				if(i%_==0)break;
				cnt[va[qu(i)]]=0,cnt2[va[qu(i)]/_]=0;
			}
			for(int i=r;i>=l;i--){
				if((i+1)%_==0)break;
				cnt[va[qu(i)]]=0,cnt2[va[qu(i)]/_]=0;
			}
			putchar('\n');
		}
		else{
			read(x),read(y);
			if(x==y)continue;
			int ll=(l-1)/_+1,rr=(r+1)/_-1;
			if(ll>rr+1){
				rebuild(rr+1,x,y,l,r);
				recoo(x,y);
				continue;
			}
			rebuild(ll-1,x,y,l,ll*_-1);
			rebuild(rr+1,x,y,(rr+1)*_,r);
			gor(ll,rr,x,y);
			recoo(x,y);
		}
	}
}