#include <bits/stdc++.h>
using i64 = int64_t;
using u32 = uint32_t;
using u64 = uint64_t;
constexpr int S = 4096;
constexpr int N = 131072;
constexpr int inf = 1e9;
int n, m, a[N], pos[N], pre[N], nxt[N];
int cnt[N], cntcnt[N], head, ans[N];
struct query {
	int l, r, k, i, t;
	bool operator <(const query &rhs) const {
		if (pos[l] != pos[rhs.l]) {
			return pos[l] < pos[rhs.l];
		} else {
			if (pos[r] != pos[rhs.r]) {
				return pos[r] < pos[rhs.r];
			} else {
				return t < rhs.t;
			}
		}
	}
};
struct modify {
	int x, y;
};
query qq[N];
int qcnt = 0;
modify mm[N];
int mcnt = 0;
void link(int x) {
	if (cntcnt[x] == 0) {
		pre[head] = x;
		nxt[x] = head;
		head = x;
	}
	cntcnt[x]++;
}
void linkdel(int x) {
	--cntcnt[x];
	if (cntcnt[x] == 0) {
		if (x == head) {
			head = nxt[x];
		}
		pre[nxt[x]] = pre[x];
		nxt[pre[x]] = nxt[x];
		nxt[x] = pre[x] = 0;
	}
}
void move(int x) {
	if (cnt[x]) {
		linkdel(cnt[x]);
	}
	++cnt[x];
	link(cnt[x]);
}
void remove(int x) {
	linkdel(cnt[x]);
	--cnt[x];
	if (cnt[x]) {
		link(cnt[x]);
	}
}
void timego(int t, int l, int r) {
	if (mm[t].x >= l && mm[t].x <= r) {
		move(mm[t].y);
		remove(a[mm[t].x]);
	}
	std::swap(a[mm[t].x], mm[t].y);
}
int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	std::cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		std::cin >> a[i];
	}
	for (int i = 1; i <= m; i++) {
		int op;
		std::cin >> op;
		if (op == 1) {
			++qcnt;
			qq[qcnt].i = qcnt;
			int l, r, k;
			std::cin >> l >> r >> k;
			qq[qcnt].l = l;
			qq[qcnt].r = r;
			qq[qcnt].k = k;
			qq[qcnt].t = mcnt;
		} else {
			++mcnt;
			int x, y;
			std::cin >> x >> y;
			mm[mcnt] = (modify){x, y};
		}
	}
	for (int i = 1; i <= n; i++) {
		pos[i] = (i - 1) / S + 1;
	}
	std::sort(qq + 1, qq + qcnt + 1);
	for (int i = 1; i <= qcnt; i++) {
		ans[i] = inf;
	}
	int l = 1, r = 0;
	for (int i = 1; i <= qcnt; i++) {
		while (l > qq[i].l) {
			move(a[--l]);
		}
		while (r < qq[i].r) {
			move(a[++r]);
		}
		while (l < qq[i].l) {
			remove(a[l++]);
		}
		while (r > qq[i].r) {
			remove(a[r--]);
		}
		static int t = 0;
		while (t < qq[i].t) {
			timego(++t, l, r);
		}
		while (t > qq[i].t) {
			timego(t--, l, r);
		}
		static int ii = 0;
		static int aa[N];
		ii = 0;
		for (int j = head; j; j = nxt[j]) {
			aa[++ii] = j;
		}
		std::sort(aa + 1, aa + ii + 1);
		int r = 1, sum = cntcnt[aa[1]];
		for (int j = 1; j <= ii; j++) {
			while (r <= ii && sum < qq[i].k) {
				++r;
				sum += cntcnt[aa[r]];
			}
			if (r > ii) {
				break;
			} else {
				ans[qq[i].i] = std::min(ans[qq[i].i], aa[r] - aa[j]);
				sum -= cntcnt[aa[j]];
			}
		}
		if (ans[qq[i].i] == inf) {
			ans[qq[i].i] = -1;
		}
	}
	for (int i = 1; i <= qcnt; i++) {
		std::cout << ans[i] << "\n";
	}
	return 0;
}
