#include <stdio.h>
#include <sys/time.h>

#define N	100000
#define Q	100000
#define A	100000
#define B	4096
#define INF	0x3f3f3f3f

int min(int a, int b) { return a < b ? a : b; }

unsigned int X;

void srand_() {
	struct timeval tv;

	gettimeofday(&tv, NULL);
	X = tv.tv_sec ^ tv.tv_usec;
	if (X % 2 == 0)
		X++;
}

int rand_() {
	return (X *= 3) >> 1;
}

int tt[Q], ll[Q], rr[Q], kk[Q], ans[Q];

int compare(int h1, int h2) {
	return h1 / B != h2 / B ? h1 / B - h2 / B : (ll[h1] / B != ll[h2] / B ? ll[h1] / B - ll[h2] / B : rr[h1] - rr[h2]);
}

void sort(int *hh, int l, int r) {
	while (l < r) {
		int i = l, j = l, k = r, h = hh[l + rand_() % (r - l)], tmp;

		while (j < k) {
			int c = compare(hh[j], h);

			if (c == 0)
				j++;
			else if (c < 0) {
				tmp = hh[i], hh[i] = hh[j], hh[j] = tmp;
				i++, j++;
			} else {
				k--;
				tmp = hh[j], hh[j] = hh[k], hh[k] = tmp;
			}
		}
		sort(hh, l, i);
		l = k;
	}
}

int kk_[N + 1], prev[N + 1], next[N + 1];

void incr(int i) {
	if (next[i] != i + 1) {
		prev[i + 1] = i, next[i + 1] = next[i];
		next[i] = i + 1;
		if (next[i + 1] != -1)
			prev[next[i + 1]] = i + 1;
	}
	kk_[i + 1]++;
	if (--kk_[i] == 0) {
		if (prev[i] != -1)
			next[prev[i]] = next[i];
		if (next[i] != -1)
			prev[next[i]] = prev[i];
	}
}

void decr(int i) {
	if (prev[i] != i - 1) {
		next[i - 1] = i, prev[i - 1] = prev[i];
		prev[i] = i - 1;
		if (prev[i - 1] != -1)
			next[prev[i - 1]] = i - 1;
	}
	kk_[i - 1]++;
	if (--kk_[i] == 0) {
		if (prev[i] != -1)
			next[prev[i]] = next[i];
		if (next[i] != -1)
			prev[next[i]] = prev[i];
	}
}

int solve(int k) {
	int ans, i, j;

	ans = INF;
	for (i = next[0], j = 0; i != -1; i = next[i]) {
		while (next[j] != -1 && k > 0)
			k -= kk_[j = next[j]];
		if (k > 0)
			break;
		ans = min(ans, j - i);
		k += kk_[i];
	}
	return ans == INF ? -1 : ans;
}

int main() {
	static int aa[N], aa_[N], old[Q], new_[Q], hh[Q], cnt[A + 1];
	int n, q, q_, h, h_, i, l, r;

	srand_();
	scanf("%d%d", &n, &q);
	for (i = 0; i < n; i++)
		scanf("%d", &aa[i]), aa_[i] = aa[i];
	q_ = 0;
	for (h = 0; h < q; h++) {
		scanf("%d", &tt[h]);
		if (tt[h] == 1) {
			scanf("%d%d%d", &ll[h], &rr[h], &kk[h]), ll[h]--, rr[h]--;
			hh[q_++] = h;
		} else {
			int a;

			scanf("%d%d", &i, &a), i--;
			ll[h] = rr[h] = i, old[h] = aa_[i], new_[h] = aa_[i] = a;
		}
	}
	sort(hh, 0, q_);
	kk_[0] = INF, prev[0] = next[0] = -1;
	for (h_ = 0, h = 0, l = 0, r = -1; h_ < q_; h_++) {
		int h1 = hh[h_], l1 = ll[h1], r1 = rr[h1];

		while (h < h1) {
			if (tt[h] == 2) {
				i = ll[h];
				if (l <= i && i <= r)
					decr(cnt[aa[i]]--);
				aa[i] = new_[h];
				if (l <= i && i <= r)
					incr(cnt[aa[i]]++);
			}
			h++;
		}
		while (h > h1) {
			h--;
			if (tt[h] == 2) {
				i = ll[h];
				if (l <= i && i <= r)
					decr(cnt[aa[i]]--);
				aa[i] = old[h];
				if (l <= i && i <= r)
					incr(cnt[aa[i]]++);
			}
		}
		while (l > l1)
			incr(cnt[aa[--l]]++);
		while (r < r1)
			incr(cnt[aa[++r]]++);
		while (l < l1)
			decr(cnt[aa[l++]]--);
		while (r > r1)
			decr(cnt[aa[r--]]--);
		ans[h1] = solve(kk[h1]);
	}
	for (h = 0; h < q; h++)
		if (tt[h] == 1)
			printf("%d\n", ans[h]);
	return 0;
}
