#include <bits/stdc++.h>
#define int long long
#define mp make_pair
#define pb push_back
#define ld long double
#define pii pair<int,int>
#define sz(x) (int)x.size()
#define piii pair<pii,pii>
#define precise cout<<fixed<<setprecision(10)
#define st first
#define nd second
#define ins insert
#define vi vector<int>
#define BOOST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
const int SQRT=(int)pow(100000,(ld)2/(ld)3)*2;
const int MAX=1e5+5;
const int inf=1e18+9;
int a[MAX];
int ans[MAX];
int b[MAX];
struct query{
	int l,r,k,czas,id;
};
vector<query>Q;
struct upd{
	int pos,val,popr;
};
vector<upd>U;
int licznikupd=0,licznikid=0;
bool cmp(query q1,query q2){
	if (q1.l/SQRT!=q2.l/SQRT)return q1.l<q2.l;
	if (q1.r/SQRT!=q2.r/SQRT)return q1.r<q2.r;
	return q1.czas<q2.czas;
}

int L=1,R=0,updates=0;

int cnt[MAX]; // ile danego koloru
int ilecnt[MAX]; // dla licznika cnt ile kolorow ma licznik
bool isin[MAX];
vi dis;
void add(int pos){
  pos=a[pos];
  ilecnt[cnt[pos]]--;
  cnt[pos]++;
  if (cnt[pos])
  ilecnt[cnt[pos]]++;
  if (cnt[pos])
  dis.pb(cnt[pos]);
}

void del(int pos){
  pos=a[pos];
  if (cnt[pos])
  ilecnt[cnt[pos]]--;
  cnt[pos]--;
  if (cnt[pos])
  ilecnt[cnt[pos]]++;
  if (cnt[pos])
  dis.pb(cnt[pos]);
}

void addupd(int pos){
  int pozycja=U[pos].pos;
  if (pozycja>=L && pozycja<=R)
  del(pozycja);
  a[U[pos].pos]=U[pos].val;
  if (pozycja>=L && pozycja<=R)add(pozycja);
}

void delupd(int pos){
  int pozycja=U[pos].pos;
  if (pozycja>=L && pozycja<=R)
  del(pozycja);
  a[U[pos].pos]=U[pos].popr;
  if (pozycja>=L && pozycja<=R)add(pozycja);
}

void solve(vi &v,int &dla,int &threshold){
	int mini=inf;
	int total=0;
	int wsk=0,last=0;
	for (int i=0;i<sz(v);i++){
	  while (wsk<sz(v) && total<threshold)total+=ilecnt[v[wsk]],last=wsk,wsk++;
	  if (total>=threshold){
		mini=min(mini,v[last]-v[i]);
	  }
	  total-=ilecnt[v[i]];
	}
	int answer=-1;
	if (mini!=inf)answer=mini;
	ans[dla]=answer;
}
int32_t main(){
  BOOST;
  int n,m;
  cin>>n>>m;
  for (int i=1;i<=n;i++)cin>>a[i],b[i]=a[i];
  for (int i=1;i<=m;i++){
    int type;
    cin>>type;
    if (type==1){
		int l,r,k;
		cin>>l>>r>>k;
		licznikid++;
		Q.pb({l,r,k,licznikupd,licznikid});
    }
    else{
		int p,x;
		cin>>p>>x;
		licznikupd++;
		U.pb({p,x,b[p]});
		b[p]=x;
    }
  }
  sort(Q.begin(),Q.end(),cmp);
  for (auto it:Q){
    while (updates<it.czas)addupd(updates++);
    while (updates>it.czas)delupd(--updates);
	while (R<it.r)add(++R);
	while (L>it.l)add(--L);
	while (R>it.r)del(R--);
	while (L<it.l)del(L++);
	vi przepisz;
	przepisz.clear();
	for (auto iter:dis){
		if (ilecnt[iter] && !isin[iter])przepisz.pb(iter),isin[iter]=true;
	}
	dis=przepisz;
	sort(dis.begin(),dis.end());
	for (auto iter:dis)isin[iter]=false;
	solve(dis,it.id,it.k);
  }
  for (int i=1;i<=licznikid;i++)cout<<ans[i]<<"\n";
  return 0; 
}

