#include<bits/stdc++.h>
using namespace std;
int read() {
	char c=getchar(); int x=0,f=1;
	while (c<'0' || c>'9') {
		if (c=='-') f=-1;
		c=getchar();
	}
	while (c>='0' && c<='9') {
		x=x*10+c-'0';
		c=getchar();
	}
	return x*f;
}
int block;
const int inf=1<<29;
struct query {
	int l,r,k,c,id;
}q[100005];
int qcnt=0;
struct change {
	int p,x;
}c[100005];
int ccnt=0;
int belong[100005];
bool cmp(query x,query y) {
	if (belong[x.l]!=belong[y.l]) return belong[x.l]<belong[y.l];
	if (belong[x.r]!=belong[y.r]) return belong[x.r]<belong[y.r];
	if (x.c!=y.c) return x.c<y.c;
}
int L,R,C;
int a[100005],cnt[100005],tot[100005],res[100005],vis[100005];
vector<int> last;
void add(int x) {
	x=a[x];
	--tot[cnt[x]];
	++cnt[x];
	++tot[cnt[x]];
	if (cnt[x]>0) last.push_back(cnt[x]);
}
void sub(int x) {
	x=a[x];
	--tot[cnt[x]];
	--cnt[x];
	++tot[cnt[x]];
	if (cnt[x]>0) last.push_back(cnt[x]);
}
void modify(int x) {
	if (L<=c[x].p && c[x].p<=R) {
		sub(c[x].p);
		swap(c[x].x,a[c[x].p]);
		add(c[x].p);
	}
	else swap(c[x].x,a[c[x].p]);
}
int main() {
	int n=read(),m=read();
	for (int i=1; i<=n; i++) a[i]=read();
	block=2200;
	for (int i=1; i<=n; i++) belong[i]=i/block;
	for (int i=1; i<=m; i++) {
		int opt=read();
		if (opt==1) {
			q[++qcnt].l=read();
			q[qcnt].r=read();
			q[qcnt].k=read();
			q[qcnt].c=ccnt;
			q[qcnt].id=qcnt;
		}
		else {
			c[++ccnt].p=read();
			c[ccnt].x=read();
		}
	}
	sort(q+1,q+qcnt+1,cmp);
	L=1,R=0,C=0;
	for (int i=1; i<=qcnt; i++) {
		while (L>q[i].l) add(--L);
		while (R<q[i].r) add(++R);
		while (L<q[i].l) sub(L++);
		while (R>q[i].r) sub(R--);
		while (C<q[i].c) modify(++C);
		while (C>q[i].c) modify(C--);
		vector<int> now;
		for (int j=0; j<last.size(); j++) {
			int t=last[j];
			if (vis[t]!=i && tot[t]>0) now.push_back(t),vis[t]=i;
		}
		sort(now.begin(),now.end());
		last=now;
		int r=0,sum=0,ans=inf;
		for (int l=0; l<now.size(); l++) {
			while (r<now.size() && sum<q[i].k) {
				sum+=tot[now[r]];
				++r;
			}
			if (sum>=q[i].k) ans=min(ans,now[r-1]-now[l]);
			sum-=tot[now[l]];
		}
		if (ans==inf) res[q[i].id]=-1;
		else res[q[i].id]=ans;
	}
	for (int i=1; i<=qcnt; i++) printf("%d\n", res[i]);
	return 0;
}