#include<bits/stdc++.h>
#define dd(x) cout<<#x<<" = "<<x<<" "
#define de(x) cout<<#x<<" = "<<x<<endl
#define de_arr(a,s,t) cout<<#a<<": ";for (int z=(s);z<=(t);++z)cout<<a[z]<<" ";cout<<endl;
#define sz(x) int(x.size())
#define All(x) x.begin(),x.end()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> P;
const double eps=1e-8;
const int mod=1e9+7;
inline int sign(double x){return (x>eps)-(x<-eps);}
inline int add(int a,int b){a+=b;return a<0?a+mod:a>=mod?a-mod:a;}
inline int mul(ll a,ll b){return a*b%mod;}
const int maxn=3e5+10,INF=0x3f3f3f3f;
int bl[maxn],B;
struct Q{
	int l,r,k,tim,id;
	Q(int _l,int _r,int _k,int _t,int _id):l(_l),r(_r),k(_k),tim(_t),id(_id){} 
	bool operator <(const Q& t)const{
		if (bl[l]^bl[t.l])	return l<t.l;
		if (bl[r]^bl[t.r])	return r<t.r;
		return tim<t.tim;
	}	
};
vector<Q> qry;
vector<P> chg;
struct node{
	int x,ne,pre,l,r;
	node(){}
	node(int _x,int _l,int _r):x(_x),l(_l),r(_r){}
}lis[maxn];
int hd,tl;
queue<int> buf;
inline int ID(){
	int t=buf.front();
	buf.pop();
	return t;
}
inline void link(int x,int y){lis[x].ne=y,lis[y].pre=x;}
int a[maxn],cnt[maxn],idx[maxn];
void init(){
	memset(idx,-1,sizeof(idx));
	for (int i=0;i<maxn;++i)	buf.push(i);
	hd=ID(),tl=ID();
	int id=ID();
	lis[idx[0]=id]=node(0,1,maxn-1);
	link(hd,id),link(id,tl);
}
inline void Add(int x){
	cnt[x]++;
	int p=idx[cnt[x]-1];
	if (idx[cnt[x]]==-1){
		int id=ID();
		lis[idx[cnt[x]]=id]=node(cnt[x],lis[p].r,lis[p].r);
		int nxt=lis[p].ne;
		link(p,id),link(id,nxt);
	}
	else
		lis[idx[cnt[x]]].l=lis[p].r;
	lis[p].r--;
	if (lis[p].r<lis[p].l){
		buf.push(p);
		idx[cnt[x]-1]=-1;
		int pre=lis[p].pre,nxt=lis[p].ne;
		link(pre,nxt);
	}
}
inline void Del(int x){
	cnt[x]--;
	int p=idx[cnt[x]+1];
	if (idx[cnt[x]]==-1){
		int id=ID();
		lis[idx[cnt[x]]=id]=node(cnt[x],lis[p].l,lis[p].l);
		int pre=lis[p].pre;
		link(pre,id),link(id,p);
	}
	else
		lis[idx[cnt[x]]].r=lis[p].l;
	lis[p].l++;
	if (lis[p].r<lis[p].l){
		buf.push(p);
		idx[cnt[x]+1]=-1;
		int pre=lis[p].pre,nxt=lis[p].ne;
		link(pre,nxt);
	}
}
inline void upd(int l,int r,int t){
	int pos=chg[t].fi,x=chg[t].se;
	if (pos>=l&&pos<=r)
		Del(a[pos]),Add(x);
	swap(a[pos],chg[t].se); 
}
int cal(int k){
	int num=0,dif=INF;
	for (int i=lis[hd].ne,j=hd;i!=tl;i=lis[i].ne){
		if (lis[i].x==0)	continue;
		while (j!=tl&&num<k){
			j=lis[j].ne;
			if (lis[j].x>0)
				num+=lis[j].r-lis[j].l+1;
		}
		if (num>=k)
			dif=min(dif,lis[j].x-lis[i].x);
		num-=lis[i].r-lis[i].l+1;
	}
	return dif==INF?-1:dif;
}
int ans[maxn];
void Mo(int n,int m){
	init();
	B=pow(1.0*n*m,1.0/3);
	for (int i=1;i<=n;++i)	bl[i]=i/B;
	sort(All(qry));
	int l=1,r=0,t=-1;
	for (auto i:qry){
		while (l>i.l)	Add(a[--l]);
		while (r<i.r)	Add(a[++r]);
		while (l<i.l)	Del(a[l++]);
		while (r>i.r)	Del(a[r--]);
		while (t<i.tim)	upd(l,r,++t);
		while (t>i.tim)	upd(l,r,t--);
		ans[i.id]=cal(i.k);
	}
}
int main()
{
	int n,m;
	cin>>n>>m;
	for (int i=1;i<=n;++i)	scanf("%d",&a[i]);
	for (int i=1;i<=m;++i){
		int op,x,y,k;
		scanf("%d%d%d",&op,&x,&y);
		if (op==1){
			scanf("%d",&k);
			qry.pb(Q(x,y,k,sz(chg)-1,i));
		}
		else
			chg.pb(mp(x,y));
	}
	memset(ans,INF,sizeof(ans));
	Mo(n,m);
	for (int i=1;i<=m;++i)
		if (ans[i]!=INF)	printf("%d\n",ans[i]); 
	return 0;
}
