天天T，天天T。调了2个晚上了，求调。

//writer:Oier_szc

#include <bits/stdc++.h>
#include <windows.h>
#define ED cerr<<endl;
#define TS cerr<<"I AK IOI"<<endl;
#define cr(x) cerr<<x<<endl;
#define cr2(x,y) cerr<<x<<" "<<y<<endl;
#define cr3(x,y,z) cerr<<x<<" "<<y<<" "<<z<<endl;
//#define int long long
using namespace std;
const int N=2e5+10,INF=2e9,mod=1e9+7,t=1e5+5;
int n,m,len=0,len2=0;
int a[N];
int st[N],ed[N],bel[N],sq,num;
int pre[N],nxt[N],w[N];
int cnt[N],tmp[N],len3=0;
int ans[N];
void insert(int id)
{
	nxt[pre[t]]=id,pre[id]=pre[t];
	nxt[id]=t,pre[t]=id;
}
void erase(int id)
{
	nxt[pre[id]]=nxt[id],pre[nxt[id]]=pre[id];
}
struct node
{
	int qid,l,lid,r,rid,k,t;
	bool operator<(const node &W) const
	{
		if(lid==W.lid) 
		{
			if(rid==W.rid) return t<W.t;
			else return rid<W.rid;
		}
		else return lid<W.lid;
	}
}q[N];
struct node2
{
	int pos,x;
}ud[N];
void add(int x)
{
	--w[cnt[x]];
	if(cnt[x]>0&&!w[cnt[x]]) erase(cnt[x]);
	++cnt[x];
	if(cnt[x]>0&&!w[cnt[x]]) insert(cnt[x]);
	++w[cnt[x]];
}
void del(int x)
{
	--w[cnt[x]];
	if(cnt[x]>0&&!w[cnt[x]]) erase(cnt[x]);
	--cnt[x];
	if(cnt[x]>0&&!w[cnt[x]]) insert(cnt[x]);
	++w[cnt[x]];
}
int get(int k)
{
	len3=0;
	int res=1e9;
	for(int i=nxt[0];i!=t;i=nxt[i]) tmp[++len3]=i;
	sort(tmp+1,tmp+1+len3);
	for(int l=1,r=1,now=0;r<=len3;++r)
	{
		now+=w[tmp[r]];
		while(l<r&&now-w[tmp[l]]>=k) now-=w[tmp[l]],++l;
		if(now>=k) res=min(res,tmp[r]-tmp[l]);
	}
	return res!=1e9?res:-1;
}

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i) scanf("%d",&a[i]);
	sq=pow(n,0.666),num=(n-1)/sq+1;
	for(int i=1;i<=num;++i)
	{
		st[i]=(i-1)*sq+1,ed[i]=min(n,i*sq);
		for(int j=st[i];j<=ed[i];++j) bel[j]=i;
	}
	int op;
	for(int i=1;i<=m;++i)
	{
		scanf("%d",&op);
		if(op==1)
		{
			++len;
			scanf("%d%d%d",&q[len].l,&q[len].r,&q[len].k);
			q[len].lid=bel[q[len].l],q[len].rid=bel[q[i].r];
			q[len].qid=len,q[len].t=len2;
		}
		else
		{
			++len2;
			scanf("%d%d",&ud[len2].pos,&ud[len2].x);
		}
	}
	sort(q+1,q+1+len);
	int id;
	insert(0);
	for(int i=1,l=1,r=0,t=0;i<=len;++i)
	{
		while(r<q[i].r) add(a[++r]);
		while(r>q[i].r) del(a[r--]);
		while(l>q[i].l) add(a[--l]);
		while(l<q[i].l) del(a[l++]);
		while(t<q[i].t)
		{
			++t,id=ud[t].pos;
			if(l<=id&&id<=r) del(a[id]),add(ud[t].x);
			swap(a[id],ud[t].x);
		}
		while(t>q[i].t)
		{
			id=ud[t].pos;
			if(l<=id&&id<=r) del(a[id]),add(ud[t].x);
			swap(a[id],ud[t].x),--t;
		}
		ans[q[i].qid]=get(q[i].k);
	}
	for(int i=1;i<=len;++i) printf("%d\n",ans[i]);
	return 0;
}