#define LOCAL
#include<bits/stdc++.h>
using namespace std;

namespace ly{
    namespace IO{
        #ifndef LOCAL
            #define SIZE (1<<20)
            char in[SIZE],out[SIZE],*p1=in,*p2=in,*p3=out;
            #define getchar() (p1==p2&&(p2=(p1=in)+fread(in,1,SIZE,stdin),p1==p2)?EOF:*p1++)
            #define flush() (fwrite(p3=out,1,SIZE,stdout))
            #define putchar(ch) (p3==out+SIZE&&flush(),*p3++=(ch))
            class Flush{public:~Flush(){flush();}}_;
        #endif
        template<typename type>
        inline void read(type &x){
            x=0;bool flag(0);char ch=getchar();
            while(!isdigit(ch)) flag^=ch=='-',ch=getchar();
            while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
            flag?x=-x:0;
        }
        template<typename type>
        inline void write(type x,bool flag=1){
            x<0?x=-x,putchar('-'):0;static short Stack[50],top(0);
            do Stack[++top]=x%10,x/=10;while(x);
            while(top) putchar(Stack[top--]|48);
            flag?putchar('\n'):putchar(' ');
        }
        #ifndef LOCAL
            #undef SIZE
            #undef getchar
            #undef putchar
            #undef flush
        #endif
    }
}using namespace ly::IO;


const int N=100010,vB=400,B=400,M=260;
int pl[M],pr[M];
int vl[M],vr[M],tot1,tot2;
int cnt1[M][M],cnt2[M][N];
int tmp1[M],tmp2[N];
int a[N],id[N],idv[N];
int fa[N],val[N],repr[M][N];
int pre[N];
int find(int x){
	return (x==fa[x]?x:fa[x]=find(fa[x]));
}
inline void exchange(int x){
	a[x]=val[find(x)];
}
inline void xchange(int Id,int x,int y,int l,int r){
	for(int i=pl[Id];i<=pr[Id];i++)
		exchange(i);
	int sxy=0;
	for(;l<=r;l++){
		if(a[l]==x){
			a[l]=y;
			sxy++;
			cnt1[Id][idv[x]]--;
			cnt1[Id][idv[y]]++;
			cnt2[Id][x]--;
			cnt2[Id][y]++;
		}
	}
	for(int i=Id+1;i<=tot2;i++){
		cnt1[i][idv[x]]-=sxy;
		cnt1[i][idv[y]]+=sxy;
		cnt2[i][x]-=sxy;
		cnt2[i][y]+=sxy;
	}
	int posx=0,posy=0;
	for(int i=pl[Id];i<=pr[Id];i++){
		if(a[i]==x){
			if(!posx)posx=i;
			else fa[i]=posx;
		}
		if(a[i]==y){
			if(!posy)posy=i;
			else fa[i]=posy;
		}
	}
	fa[posx]=posx;val[posx]=x;repr[Id][x]=posx;
	fa[posy]=posy;val[posy]=y;repr[Id][y]=posy;
}
inline void change(int L,int R,int x,int y){
	int l=L,r=R,idl=id[l],idr=id[r];
	if(id[L]==id[R]){
		xchange(id[L],x,y,l,r);
		return;
	}else{
		xchange(idl,x,y,L,pr[idl]);
		xchange(idl,x,y,pl[idr],R);	
		idl++;
		idr--;
	}
	for(int i=idl;i<=idr;i++){
		if(repr[i][x]){
			int tmp=cnt2[i][x]-cnt2[i-1][x];
			cnt1[i][idv[x]]-=tmp;
			cnt1[i][idv[y]]+=tmp;
			cnt2[i][x]-=tmp;
			cnt2[i][y]+=tmp;
			if(repr[i][y]){
				fa[repr[i][x]]=repr[i][y];
				repr[i][x]=0;
			}else{
				val[repr[i][x]]=y;
				repr[i][y]=repr[i][x];
				repr[i][x]=0;
			}
		}
	}
	int sxy=cnt2[idr][x]-cnt2[idl-1][x];
	for(int i=idr+1;i<=tot2;i++){
		cnt1[i][idv[x]]-=sxy;
		cnt1[i][idv[y]]+=sxy;
		cnt2[i][x]-=sxy;
		cnt2[i][y]+=sxy;
	}
}
inline int query(int L,int R,int k){
	int l=L,r=R;
	if(id[L]==id[R]){
		for(int i=l;i<=r;i++){exchange(i);tmp1[idv[a[i]]]++;tmp2[a[i]]++;}
		int pos=0,x=0;
		for(int i=1;i<=tot2;i++){
			if(x+tmp1[i]>=k){
				pos=i;
				break;
			}
			x+=tmp1[i];
		}
		int ans=0;
		for(int i=vl[pos];i<=vr[pos];i++){
			if(x+tmp2[i]>=k){
				ans=i;
				break;
			}
			x+=tmp2[i];
		}
		for(int i=l;i<=r;i++){tmp1[idv[a[i]]]--;tmp2[a[i]]--;}
		return ans;
	}
	int idl=id[l],idr=id[r];
	for(int i=l;i<=pr[idl];i++){exchange(i),tmp1[idv[a[i]]]++;tmp2[a[i]]++;}
	for(int i=pl[idr];i<=r;i++){exchange(i),tmp1[idv[a[i]]]++;tmp2[a[i]]++;}	
	idl++;idr--;
	int pos=0,x=0;
	for(int i=1;i<=tot2;i++){
		if(x+cnt1[idr][i]-cnt1[idl-1][i]+tmp1[i]>=k){
			pos=i;
			break;
		}
		x+=cnt1[idr][i]-cnt1[idl-1][i]+tmp1[i];
	}
	int ans=0;
	for(int i=vl[pos];i<=vr[pos];i++){
		if(x+cnt2[idr][i]-cnt2[idl-1][i]+tmp2[i]>=k){
			ans=i;
			break;
		}
		x+=cnt2[idr][i]-cnt2[idl-1][i]+tmp2[i];
	}
	idl--;idr++;
	for(int i=l;i<=pr[idl];i++){tmp1[idv[a[i]]]--;tmp2[a[i]]--;}
	for(int i=pl[idr];i<=r;i++){tmp1[idv[a[i]]]--;tmp2[a[i]]--;}
	return ans;
}
signed main(){
//	freopen("data.in","r",stdin);
//	freopen("my.out","w",stdout);
	int n,m;
    read(n);read(m);
    for(int i=1;i<=n;i++)read(a[i]),id[i]=(i+B-1)/B,fa[i]=i,val[i]=a[i];
    for(int i=1;i<=N-10;i++)idv[i]=(i+vB-1)/vB;
    tot1=id[n];tot2=idv[N-10];
    for(int i=1;i<=tot1;i++){
    	pl[i]=(i-1)*B+1;
    	pr[i]=min(i*B,n);
    	for(int j=1;j<=N-10;j++)cnt2[i][j]=cnt2[i-1][j],pre[j]=0;
    	for(int j=1;j<=tot2;j++)cnt1[i][j]=cnt1[i-1][j];
    	for(int j=pl[i];j<=pr[i];j++){
    		cnt1[i][idv[a[j]]]++;
    		cnt2[i][a[j]]++;
    		if(!pre[a[j]]){
    			pre[a[j]]=j;
    			repr[i][a[j]]=j;
    			val[j]=a[j];
			}else{
				fa[j]=pre[a[j]];
			}
		}
	}
	for(int i=1;i<=tot2;i++)vl[i]=(i-1)*vB+1,vr[i]=i*vB;
    while(m--){
    	int op,l,r;
    	read(op);read(l);read(r);
    	if(op==1){
    		int x,y;
    		read(x);read(y);
    		if(x==y)continue;
    		change(l,r,x,y);
		}else{
			int k;
			read(k);
			write(query(l,r,k));
		}
	}
    return 0;
}
/*

*/