#include<bits/stdc++.h>
using namespace std;
#define fp(i,l,r) for(register int (i)=(l);(i)<=(r);++(i))
#define fd(i,l,r) for(register int (i)=(l);(i)>=(r);--(i))
#define fe(i,u) for(register int (i)=front[(u)];(i);(i)=e[(i)].next)
#define mem(a) memset((a),0,sizeof (a))
#define O(x) cerr<<#x<<':'<<x<<endl
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
    return x*f;
}
void wr(int x){
    if(x<0)putchar('-'),x=-x;
    if(x>=10)wr(x/10);
    putchar('0'+x%10);
}
const int MAXN=1e5+10;
struct MD{
	int p,v;
}mq[MAXN];
int bel[MAXN],ans[MAXN],a[MAXN],n,Q,B,ccnt[MAXN],cnt[MAXN],mcnt,qcnt,b[1010],m;
int pre[MAXN],nxt[MAXN];
bool vis[MAXN];
struct node{
	int l,r,k,t,id;
	inline bool operator<(const node &b)const{
		if(bel[l]!=bel[b.l])return l<b.l;
		if(bel[r]!=bel[b.r])return bel[l]&1?r<b.r:r>b.r;
		return (bel[l]^bel[r])&1?t<b.t:t>b.t;
	}
}ask[MAXN];
inline void del(int x){
	if(!x)return;
	if(!--ccnt[x]){
		pre[nxt[x]]=pre[x];nxt[pre[x]]=nxt[x];
	}
	return;
}
inline void add(int x){
	if(!x)return;
	if(!ccnt[x]++)nxt[pre[n+1]]=x,pre[x]=pre[n+1],nxt[x]=n+1,pre[n+1]=x;
}
inline void md(int x){
	del(cnt[a[x]]);
	if(vis[x]^=1)add(++cnt[a[x]]);else add(--cnt[a[x]]);
}
inline void mdy(int t){
	int p=mq[t].p,v=mq[t].v;mq[t].v=a[p];
	if(vis[p])md(p),a[p]=v,md(p);
	else a[p]=v;
}
int main(){
	n=read();Q=read();B=max((int)pow(n,2.0/3.0),1);
	nxt[0]=n+1;pre[n+1]=0;
	fp(i,1,n)a[i]=read(),bel[i]=(i-1)/B+1;
	while(Q--){
		int op=read();
		if(op==1){
			int l=read(),r=read(),k=read();
			++qcnt;ask[qcnt]={l,r,k,mcnt,qcnt};
		}
		else{
			int p=read(),v=read();
			mq[++mcnt]={p,v};
		}
	}
	sort(ask+1,ask+1+qcnt);
	int l=ask[1].l,r=l-1,cur=0;
	fp(kk,1,qcnt){
		int ql=ask[kk].l,qr=ask[kk].r,t=ask[kk].t,k=ask[kk].k;
		while(cur<t)mdy(++cur);
		while(cur>t)mdy(cur--);
		while(l<ql)md(l++);while(l>ql)md(--l);
		while(r<qr)md(++r);while(r>qr)md(r--);
		m=0;for(int i=nxt[0];i!=n+1;i=nxt[i])b[++m]=i;
		sort(b+1,b+1+m);
		int p=0,ans=1e9,s=0;
		fp(i,1,m){
			if(i-1)s-=ccnt[b[i-1]];
			while(p<m&&s<k)s+=ccnt[b[++p]];
			if(s>=k)ans=min(ans,b[p]-b[i]);
		}
		if(ans==1e9)ans=-1;
		::ans[ask[kk].id]=ans;
	}
	fp(i,1,qcnt)wr(ans[i]),putchar('\n');
	return 0;
}