#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5;

struct query {
	int i, type, l, r, k, p, x;
};

int n, m;
vector<int> a, _a;
query q[N];
int queryCnt;
int block_size;
int ans[N];
int freqA[N];
int freqL[N], freqR[N], freqV[N];

void increaseFreq(int f) {
	freqR[f]++, freqL[f - 1]++, freqV[freqR[f] - 1] = f;
}

void decreaseFreq(int f) {
	freqR[f]--, freqL[f - 1]--, freqV[freqR[f]] = f - 1;
}

void include(int i) {
	increaseFreq(++freqA[a[i]]);
}

void remove(int i) {
	decreaseFreq(freqA[a[i]]--);
}

void go(int& fromL, int& fromR, int toL, int toR) {
	// debug() << name(fromL) name(fromR) name(toL) name(toR);
	while (fromL > toL) include(--fromL);
	while (fromR < toR) include(fromR++);
	while (fromL < toL) remove(fromL++);
	while (fromR > toR) remove(--fromR);
}

void update(int qi, int L, int R) {
	if (L <= q[qi].p && q[qi].p < R) remove(q[qi].p);
	a[q[qi].p] = q[qi].x;
	if (L <= q[qi].p && q[qi].p < R) include(q[qi].p);
}

int answer(int k) {
	vector<pair<int, int>> v;
	for (int at = freqV[1]; at != 0; ) {
		v.push_back({at, freqR[at] - freqL[at]});
		at = freqV[freqR[at]];
	}
	reverse(v.begin(), v.end());
	
	int ret = -1;
	for (int l = 0, r = 0, cnt = 0; l < v.size(); cnt -= v[l++].second) {
		r = max(l, r);
		while (r < v.size() && cnt < k) cnt += v[r++].second;
		if (cnt >= k) {
			int _ret = v[r - 1].first - v[l].first;
			ret = ret == -1 ? _ret : min(ret, _ret);
		}
	}
    // debug() << name(k) name(v) name(ret);
	
	return ret;
}

int main() {
	scanf("%d %d", &n, &m);
	_a.resize(n + 1);
	for (int i = 1; i <= n; i++) scanf("%d", &_a[i]); a = _a;
	for (int i = 1; i <= m; i++) {
		q[i].i = i;
		scanf("%d", &q[i].type);
		if (q[i].type == 1) scanf("%d %d %d", &q[i].l, &q[i].r, &q[i].k);
		else scanf("%d %d", &q[i].p, &q[i].x);
		queryCnt += q[i].type == 1;
	}
	
	block_size = ceil(cbrt((long double)2 * n * n));
	
	sort(q + 1, q + m + 1, [](const query& q1,const query& q2) {
		int l1 = (q1.l - 1) / block_size, r1 = (q1.r - 1) / block_size;
		int l2 = (q2.l - 1) / block_size, r2 = (q2.r - 1) / block_size;
		auto p1 = make_pair(l1, r1);
		auto p2 = make_pair(l2, r2);
		
		if (q1.type == 1) {
			if (q2.type == 1) return make_pair(p1, q1.i) < make_pair(p2, q2.i);
			else return true;
		} else {
			if (q2.type == 1) return false;
			else return q1.i < q2.i;
		}
	});
	
	// for (int i = 1; i <= m; i++) debug() << name(i) name(q[i].type) name(q[i].i);
	
	fill(ans, ans + N, -2);
	fill(freqL, freqL + N, 1);
	fill(freqR, freqR + N, 1);
	freqR[0] = N;
	
	pair<int, int> qp = {-1, -1};
	int qAt;
	int L = 1, R = 1;
	for (int i = 1; i <= m && q[i].type == 1; i++) {
		int ql = (q[i].l - 1) / block_size, qr = (q[i].r - 1) / block_size;
		pair<int, int> _qp = {ql, qr};
		if (qp != _qp) {
			go(L, R, block_size * ql + 1, block_size * ql + 1);
			a = _a;
			qAt = queryCnt + 1;
			qp = _qp;
		}
		
		while (qAt <= m && q[qAt].i < q[i].i) {
			update(qAt, L, R);
			qAt++;
		}
		
		go(L, R, q[i].l, q[i].r + 1);
		
		// debug() << name(q[i].i);
		ans[q[i].i] = answer(q[i].k);
	}
	
	for (int i = 1; i <= m; i++) if (ans[i] >= -1) printf("%d\n", ans[i]);
	
	return 0;
}