#pragma GCC optimize("Ofast","-funroll-loops","-fdelete-null-pointer-checks")
#pragma GCC target("ssse3","sse3","sse2","sse","avx2","avx")
#include <iostream>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;

#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1 << 21], *p1 = buf, *p2 = buf;

inline int qread() {
	register char c = getchar();
	register int x = 0, f = 1;
	while (c < '0' || c > '9') {
		if (c == '-') f = -1;
		c = getchar();
	}
	while (c >= '0' && c <= '9') {
		x = (x << 3) + (x << 1) + c - 48;
		c = getchar();
	}
	return x * f;
}

inline int Abs(const int& x) {return (x > 0 ? x : -x);}
inline int Max(const int& x, const int& y) {return (x > y ? x : y);}
inline int Min(const int& x, const int& y) {return (x < y ? x : y);}

const int S = 3420, N = 100005;
int n, m, a[N], pos[N], pre[N], nxt[N], cnt[N], cntcnt[N], hd, ans[N], val[N], vcnt;
struct Query {
	int l, r, k, i, t;
	bool operator < (const Query& b) const {
		return (pos[l] ^ pos[b.l] ? pos[l] < pos[b.l] : (pos[r] ^ pos[b.r] ? pos[r] < pos[b.r] : t < b.t));
	}
};
Query qry[N];
int qcnt;
struct Modify {
	int x, y;
};
Modify mod[N];
int mcnt;

inline void LinkAdd(int x) {
	if (cntcnt[x] == 0) {
		//printf("Add %d\n", x);
		pre[hd] = x;
		nxt[x] = hd;
		hd = x;
	}
	cntcnt[x]++;
	pre[0] = 0;
	nxt[0] = 0;
}

inline void LinkDel(int x) {
	cntcnt[x]--;
	if (cntcnt[x] == 0) {
		//printf("Del %d\n", x);
		if (x == hd) hd = nxt[x];
		pre[nxt[x]] = pre[x];
		nxt[pre[x]] = nxt[x];
		nxt[x] = pre[x] = 0;
	}
	pre[0] = 0;
	nxt[0] = 0;
}

inline void Read() {
	n = qread(); m = qread();
	for (int i = 1;i <= n;i++) a[i] = qread();
	for (int i = 1;i <= m;i++) {
		int opt = qread();
		if (opt == 1) {
			qcnt++;
			qry[qcnt].i = qcnt;
			qry[qcnt].l = qread();
			qry[qcnt].r = qread();
			qry[qcnt].k = qread();
			qry[qcnt].t = mcnt;
		} else {
			mcnt++;
			mod[mcnt].x = qread();
			mod[mcnt].y = qread();
		}
	}
}

inline void Add(int x) {
	if (cnt[x]) LinkDel(cnt[x]);
	cnt[x]++;
	LinkAdd(cnt[x]);
}

inline void Del(int x) {
	LinkDel(cnt[x]);
	cnt[x]--;
	if (cnt[x]) LinkAdd(cnt[x]);
}

inline void Time(int t, int l, int r) {
	if (mod[t].x >= l && mod[t].x <= r) {
		Add(mod[t].y);
		Del(a[mod[t].x]);
	}
	swap(mod[t].y, a[mod[t].x]);
}

inline void Prefix() {
	for (int i = 1;i <= n;i++) pos[i] = (i - 1) / S + 1;
	sort(qry + 1, qry + qcnt + 1);
}

inline void Solve() {
	int l = 1, r = 0, t = 0;
	for (int i = 1;i <= qcnt;i++) {
		while (l > qry[i].l) Add(a[--l]);
		while (r < qry[i].r) Add(a[++r]);
		while (r > qry[i].r) Del(a[r--]);
		while (l < qry[i].l) Del(a[l++]);
		while (t < qry[i].t) Time(++t, l, r);
		while (t > qry[i].t) Time(t--, l, r);
		vcnt = 0;
		for (int j = hd;j;j = nxt[j]) val[++vcnt] = j;
		// if (qry[i].i == 8) {
		// 	printf("%d %d %d\n", l, r, t);
		// 	for (int j = 1;j <= n;j++) printf("%d ", a[j]); puts("");
		// 	for (int j = 1;j <= 10;j++) printf("%d ", cnt[j]);puts("");
		// 	for (int j = 1;j <= vcnt;j++) printf("%d ", val[j]);
		// 	puts("");
		// }
		sort(val + 1, val + vcnt + 1);
		int r = 1, sum = cntcnt[val[1]];
		ans[qry[i].i] = 0x3f3f3f3f;
		for (int j = 1;j <= vcnt;j++) {
			while (r <= vcnt && sum < qry[i].k) {
				r++;
				sum += cntcnt[val[r]];
			}
			if (r > vcnt) break;
			ans[qry[i].i] = Min(ans[qry[i].i], val[r] - val[j]);
			sum -= cntcnt[val[j]];
		}
		if (ans[qry[i].i] == 0x3f3f3f3f) ans[qry[i].i] = -1;
	}
	for (int i = 1;i <= qcnt;i++) printf("%d\n", ans[i]);
}

int main() {
	Read();
	Prefix();
	Solve();
	#ifndef ONLINE_JUDGE
	while (1);
	#endif
	return 0;
}
