#include<bits/stdc++.h>
using namespace std;
int n,q,a[100006];
int tot,tot2,B,B2,bl[405],br[405];
int bl2[405],br2[406],f[100005],repr[406][100005];
int Bl2[100005];
int cnt[405][100005],blcnt[405][405];
int get(int x){
	if(f[x]==x)return x;
	return f[x]=get(f[x]);
}
void build(int x){
	int l=bl[x],r=br[x];
	for(int i=l;i<=r;i++){
		if(repr[x][a[i]])f[i]=repr[x][a[i]];
		else{
//			val[i]=a[i];
			repr[x][a[i]]=i;
			f[i]=i;
		}
		cnt[x][a[i]]++;
	}
	for(int i=1;i<=100000;i++){
		blcnt[x][Bl2[i]]+=cnt[x][i];
		cnt[x][i]+=cnt[x-1][i];
	}
	for(int i=1;i<=tot2;i++)blcnt[x][i]+=blcnt[x-1][i];
}
void update(int ind,int l,int r,int x,int y){
	int tmp=0;
//	cout<<ind<<" "<<l<<" "<<r<<" "<<x<<" "<<y<<endl;
	repr[ind][x]=0;
	for(int i=bl[ind];i<=br[ind];i++){
		a[i]=a[get(i)];
		
		if(a[i]==x){
			if(l<=i&&i<=r){
				tmp++;
				a[i]=y;
				if(repr[ind][y])f[i]=repr[ind][y];
				else {
					repr[ind][y]=i;
					a[i]=y;
					f[i]=i;
				}
			}else{
				if(repr[ind][x])f[i]=repr[ind][x];
				else {
					repr[ind][x]=i;
					a[i]=x;
					f[i]=i;
				}
			}
		}
//		cout<<a[i]<<" ";
	}
//	cout<<endl;
	for(int i=ind;i<=tot;i++){
		cnt[i][x]-=tmp;
		blcnt[i][Bl2[x]]-=tmp;
		cnt[i][y]+=tmp;
		blcnt[i][Bl2[y]]+=tmp;
	}
}
void merge(int B,int x,int y){
	if(repr[B][x]==0)return;
	f[repr[B][x]]=repr[B][y];
	repr[B][x]=0;
	blcnt[B][Bl2[x]]-=cnt[B][x];
	blcnt[B][Bl2[y]]+=cnt[B][y];
	cnt[B][y]+=cnt[B][x];
	cnt[B][x]=0;
}
void change(int l,int r,int x,int y){
	if(x==y)return;
	int L=(l-1)/B+1,R=(r-1)/B+1;
	if(L==R){
		update(L,l,r,x,y);
		return;
	}
	update(L,l,br[L],x,y);
	update(R,bl[R],r,x,y);
	for(int i=tot;i>=L+1;i--){
		cnt[i][x]-=cnt[i-1][x];
		blcnt[i][Bl2[x]]-=blcnt[i-1][Bl2[x]];
		cnt[i][y]-=cnt[i-1][y];
		blcnt[i][Bl2[y]]-=blcnt[i-1][Bl2[y]];
	}
	for(int i=L+1;i<=tot;i++){
		merge(i,x,y);
		cnt[i][x]+=cnt[i-1][x];
		blcnt[i][Bl2[x]]+=blcnt[i-1][Bl2[x]];
		cnt[i][y]+=cnt[i-1][y];
		blcnt[i][Bl2[y]]+=blcnt[i-1][Bl2[y]];
	}
}
int s[405],c[100005];
void query(int l,int r,int k){
	int L=(l-1)/B+1,R=(r-1)/B+1;
//	cout<<L<<" "<<R<<endl;
	if(L==R){
		for(int i=l;i<=r;i++){
			a[i]=a[get(i)];
			s[Bl2[a[i]]]++;
			c[a[i]]++;
		}
		int sum=0;
		int pos=0;
		while(pos<tot2){
			sum+=s[++pos];
			if(sum>=k){
				sum-=s[pos];
				break;
			}
		}
		for(int i=bl2[pos];i<=br2[pos];i++){
			sum+=c[i];
			if(sum>=k){
				cout<<i<<"\n";
				break;
			}
		}
		for(int i=l;i<=r;i++){
			s[Bl2[a[i]]]--;
			c[a[i]]--;
		}
	}else{
		
		for(int i=l;i<=br[L];i++){
			a[i]=a[get(i)];
			s[Bl2[a[i]]]++;
			c[a[i]]++;
//			cout<<a[i]<<" ";
		}
//		cout<<R<<" "<<r<<endl;
		for(int i=bl[R];i<=r;i++){
			a[i]=a[get(i)];
			s[Bl2[a[i]]]++;
			c[a[i]]++;
//			cout<<a[i]<<" ";
		}
//		cout<<endl;
		int sum=0;
		int pos=0;
		while(pos<tot2){
			pos++;
//			cout<<"add "<<pos<<" "<<s[pos]+(blcnt[R-1][pos]-blcnt[L][pos])<<endl;
			sum+=s[pos]+(blcnt[R-1][pos]-blcnt[L][pos]);
			if(sum>=k){
				sum-=s[pos]+(blcnt[R-1][pos]-blcnt[L][pos]);
				break;
			}
		}
//		cout<<sum<<endl;
		for(int i=bl2[pos];i<=br2[pos];i++){
			sum+=c[i]+(cnt[R-1][i]-cnt[L][i]);
//			cout<<i<<" "<<c[i]<<endl;
			if(sum>=k){
				cout<<i<<"\n";
				break;
			}
		}
		for(int i=l;i<=br[L];i++){
			s[Bl2[a[i]]]--;
			c[a[i]]--;
		}
		for(int i=bl[R];i<=r;i++){
			s[Bl2[a[i]]]--;
			c[a[i]]--;
		}
	}
}
int main(){
//	ios::sync_with_stdio(0);
//	cin.tie(0),cout.tie(0);
	cin>>n>>q;
	B=sqrt(n)+1;
	B2=sqrt(100000);
	bl[1]=1;
	tot=1;

	while(bl[tot]+B<=n){
		br[tot]=bl[tot]+B-1;
		tot++;
		bl[tot]=br[tot-1]+1;
	}
	br[tot]=n;
	bl2[1]=1;
	tot2=1;
	while(bl2[tot2]+B2<=100000){
		br2[tot2]=bl2[tot2]+B2-1;
		tot2++;
		bl2[tot2]=br2[tot2-1]+1;
	}
	for(int i=1;i<=tot2;i++)for(int j=bl2[i];j<=br2[i];j++)Bl2[j]=i;
	br2[tot2]=100000;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<=tot;i++)build(i);
//	for(int i=1;i<=tot;i++){
//		for(int j=1;j<=3;j++)cout<<cnt[i][j]<<" ";
////		cout<<endl;
//	}
//	cout<<endl;
	while(q--){
		int opt,l,r;
		cin>>opt>>l>>r;
		if(opt==1){
			int x,y;
			cin>>x>>y;
			change(l,r,x,y);
		}else{
			int k;
			cin>>k;
			query(l,r,k);
		}
	}
}