#include<bits/stdc++.h>
#define N 100000
using namespace std;
inline int read(){
	int res=0;char c=getchar(),f=1;
	while(c<48||c>57){if(c=='-')f=0;c=getchar();}
	while(c>=48&&c<=57)res=(res<<3)+(res<<1)+(c&15),c=getchar();
	return f?res:-res;
}inline void write(int x){
	char ch[20];ch[0]=0;
	while(x)ch[++ch[0]]=x%10+'0',x/=10;
	while(ch[0])putchar(ch[ch[0]--]);
}
int a[N+5],B,B2,cntt,cntt2;
int be[405],ed[405],cnt[405][405],cnt2[405][N+5],tr[405],tr2[N+5],bel[N+5];
int be2[405],ed2[405],bel2[N+5];
int rt[405][100005],fa[100005],sta[605],cnt3[405][N+5];
inline int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
inline void add_upd(int l,int r){for(int i=l; i<=r; i++)a[i]=a[find(i)],tr[bel2[a[i]]]++,tr2[a[i]]++;}

inline void build(int p){
	for(int i=be[p]; i<=ed[p]; i++){
		if(!rt[p][a[i]])rt[p][a[i]]=i;
		else fa[i]=rt[p][a[i]];
		++cnt3[p][a[i]];
		++cnt2[p][a[i]];++cnt[p][bel2[a[i]]];bel[i]=p;
	}
}
inline void update(int p,int l,int r,int x,int y){
	int tmp=0,l0=be[p],r0=ed[p],top=0;
	rt[p][x]=rt[p][y]=0;
	for(int i=l0; i<=r0; ++i){
		a[i]=a[find(i)];
		if(a[i]==x||a[i]==y)sta[++top]=i;
	}for(int i=l; i<=r; ++i)if(a[i]==x)a[i]=y,++tmp;
	for(int i=1; i<=top; ++i)fa[sta[i]]=sta[i];
	for(int i=1,t,w; i<=top; ++i){
		t=sta[i],w=a[t];
		if(!rt[p][w])rt[p][w]=t;
		else fa[t]=rt[p][w];
	}cnt3[p][x]-=tmp,cnt3[p][y]+=tmp;
	for(int i=p; i<=cntt; ++i){
		cnt2[i][x]-=tmp,cnt2[i][y]+=tmp;
		if(bel2[x]!=bel2[y])cnt[i][bel2[x]]-=tmp,cnt[i][bel2[y]]+=tmp;
	}
}
int main(){
//	freopen("LV.in","r",stdin); 
	int n=read(),m=read(); 
	for(int i=1; i<=n; i++)a[i]=read(),fa[i]=i;
	B=600;cntt=n/B;if(n%B)cntt++;
	B2=600;cntt2=N/B2;if(N%B2)cntt2++;
	for(int i=1; i<=cntt2; i++){
		be2[i]=ed2[i-1]+1;ed2[i]=min(N,be2[i]+B2-1);
		for(int j=be2[i]; j<=ed2[i]; j++)bel2[j]=i;
	}for(int i=1; i<=cntt; i++){
		be[i]=ed[i-1]+1;ed[i]=min(n,be[i]+B-1);
		for(int j=1; j<=cntt2; j++)cnt[i][j]=cnt[i-1][j];
		for(int j=1; j<=N; j++)cnt2[i][j]=cnt2[i-1][j];
		build(i);
	}while(m--){
		int op=read(),l=read(),r=read(),x,y,k;
		if(op==2){
			k=read();
//			cout<<op<<" "<<l<<" "<<r<<" "<<x<<endl;
			int posl=bel[l],posr=bel[r];
			if(posl==posr)add_upd(l,r);
			else add_upd(l,ed[posl]),add_upd(be[posr],r);
			int now=k,id,ans;
			for(int i=1; i<=cntt2; i++){
				int tmp=tr[i];
				if(posl!=posr)tmp+=cnt[posr-1][i]-cnt[posl][i];
				if(now<=tmp){id=i;break;}
				now-=tmp; 
			}
//			for(int i=be2[id]; i<=ed2[id]; i++)tr2[i]=0;
			for(int i=be2[id]; i<=ed2[id]; i++){
				int tmp=tr2[i];
				if(posl!=posr)tmp+=cnt2[posr-1][i]-cnt2[posl][i];
				if(now<=tmp){ans=i;break;}
				now-=tmp; 
			}
//			printf("%d\n",ans);
			write(ans),putchar('\n');
			if(posl==posr)for(int i=l; i<=r; i++)tr[bel2[a[i]]]--,tr2[a[i]]--;
			else{
				for(int i=l; i<=ed[posl]; i++)tr[bel2[a[i]]]--,tr2[a[i]]--;
				for(int i=be[posr]; i<=r; i++)tr[bel2[a[i]]]--,tr2[a[i]]--;
			}
		}else{
			x=read(),y=read();
			int posl=bel[l],posr=bel[r];
			if(posl==posr)update(posl,l,r,x,y);
			else{
				update(posl,l,ed[posl],x,y),update(posr,be[posr],r,x,y);
				int tmps=0,tmp,la=cnt2[posl][x];
				for(int i=posl+1; i<posr; ++i){
					if(rt[i][x]){
						if(!rt[i][y])rt[i][y]=rt[i][x],a[rt[i][x]]=y;
						else fa[rt[i][x]]=rt[i][y];
						rt[i][x]=0;
						tmp=cnt3[i][x],tmps+=tmp;
						cnt3[i][x]=0,cnt3[i][y]+=tmp;
					}la=cnt2[i][x];
					cnt2[i][x]-=tmps,cnt2[i][y]+=tmps;
					if(bel2[x]!=bel2[y])cnt[i][bel2[x]]-=tmps,cnt[i][bel2[y]]+=tmps;
				}for(int i=posr; i<=cntt; i++){
					cnt2[i][x]-=tmps,cnt2[i][y]+=tmps;
					if(bel2[x]!=bel2[y])cnt[i][bel2[x]]-=tmps,cnt[i][bel2[y]]+=tmps;
				}
			}
		}
	}
	return 0;
} /*
10 1000
4 5 3 2 6 7 8 9 1 10

*/