#include<bits/stdc++.h>
using namespace std;
const int maxn = 1000010 ,Mx = 100000;
int read() {
	int s=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9') {if(ch=='-')w=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
	return s*w;
}
struct info{int l,r,K,n;}Q[maxn];
int B[maxn],S[maxn],C[maxn],a[maxn],Pro[maxn],L[maxn],Vb;char v[maxn];
bool cmp(info x,info y) {return B[x.l]==B[y.l]?B[x.r]==B[y.r]?x.n<y.n:x.r<y.r:x.l<y.l;}
int n,q,Q0,Qx[maxn],Qy[maxn],Qt[maxn],Qw,pr[maxn];
void ins(int x) {--S[C[x]],++S[++C[x]];}
void rem(int x) {--S[C[x]],++S[--C[x]];}
void upd(int x) {if(v[Qx[x]]) rem(a[Qx[x]]);swap(a[Qx[x]],Qy[x]);if(v[Qx[x]]) ins(a[Qx[x]]);}
int ask(int K) {
	int ans=0x7fffffff;L[0]=0;
	for(int i=1;i<=Pro[0];i++)
		if(C[Pro[i]]>Vb) L[++L[0]]=C[Pro[i]];
	sort(L+1,L+1+L[0]);
	for(int l=1,r=0,res=0;l<=Vb;l++) {
		while(r<Vb&&res<K) res+=S[++r];
		if(res<K) {
			if(K-res<=L[0]) ans=min(ans,L[K-res]-l);
			else break;
		}
		else ans=min(ans,r-l);
		res-=S[l];
	}
	for(int i=1;i+K<=L[0]+1;i++) ans=min(ans,L[i+K-1]-L[i]);
	return ans;
}
signed main() {
	memset(pr,-1,sizeof(pr));
	n=read(),q=read(),Vb=sqrt(n*log2(n));
	for(int i=1,bl=pow(n,2./3);i<=n;i++) a[i]=read(),++C[a[i]],B[i]=(i-1)/bl+1;
	for(int i=1;i<=q;i++)
		if(read()==1) Q[++Q0]=(info){read(),read(),read(),i};
		else Qx[++Qw]=read(),++C[Qy[Qw]=read()],Qt[Qw]=i;
	for(int i=1;i<=Mx;C[i++]=0)
		if(C[i]>Vb) Pro[++Pro[0]]=i;
	sort(Q+1,Q+1+Q0,cmp);
	int L=1,R=0,ti=0;
	for(int i=1;i<=Q0;i++) {
		while(R<Q[i].r) ins(a[++R]),v[R]=1;
		while(Q[i].l<L) ins(a[--L]),v[L]=1;
		while(Q[i].r<R) v[R]=0,rem(a[R--]);
		while(L<Q[i].l) v[L]=0,rem(a[L++]);
		while(ti<Qw&&Qt[ti+1]<Q[i].n) upd(++ti);
		while(ti&&Qt[ti]>Q[i].n) upd(ti--);
		pr[Q[i].n]=ask(Q[i].K);
	}
	for(int i=1;i<=q;i++)
		if(~pr[i]) cout<<(pr[i]==0x7fffffff?-1:pr[i])<<'\n';
	return 0;
}