// Exported by Exporter.exe
#pragma GCC optimize("O3")
// Included from g.cpp
// Compile flags -Wall -Wextra -Wshadow -D_GLIBCXX_ASSERTIONS -DDEBUG -ggdb3 -fmax-errors=2
#include <bits/stdc++.h>
using namespace std;
#define PB push_back
#define F first
#define S second
#define MP make_pair
#define MTP make_tuple
typedef long long int ll;

constexpr int kN = int(1E5 + 10);
constexpr int kSq3N = 2155;
constexpr int kSq = 910;
// constexpr int kMod = 998244353;
constexpr int kInf = 0x3f3f3f3f;
// constexpr ll kInf = 0x3f3f3f3f3f3f3f3f;
// constexpr double kPi = acos(-1);
// constexpr double kEps = 1E-9;

template <typename T> T ABS(T n) {return n >= 0 ? n : -n;}


// Included from C:\Users\ianli\Desktop\CP\template\Various\Fast_IO.cpp
static inline char Get_Raw_Char() {
	static char buf[1 << 16], *p = buf, *end = buf;
	if (p == end) {
		if ((end = buf + fread(buf, 1, 1 << 16, stdin)) == buf) return '\0';
		p = buf;
	}
	return *p++;
}

static inline int Get_Digit() {
	char c = Get_Raw_Char();
	while (!isdigit(c)) c = Get_Raw_Char();
	return int(c - '0');
}

static inline int Get_PInt() {
	char c = Get_Raw_Char();
	int ret;
	while (!isdigit(c)) c = Get_Raw_Char();
	ret = int(c - '0');
	while (isdigit(c = Get_Raw_Char())) ret = ret * 10 + int(c - '0');
	return ret;
}

static inline int Get_Int() {
	char c = Get_Raw_Char();
	bool neg = false;
	int ret;
	while (!isdigit(c)) {
		if (c == '-') neg = true;
		c = Get_Raw_Char();
	}
	ret = int(c - '0');
	while (isdigit(c = Get_Raw_Char())) ret = ret * 10 + int(c - '0');
	if (neg) return -ret;
	return ret;
}

static inline long long int Get_ll() {
	char c = Get_Raw_Char();
	bool neg = false;
	long long int ret;
	while (!isdigit(c)) {
		if (c == '-') neg = true;
		c = Get_Raw_Char();
	}
	ret = int(c - '0');
	while (isdigit(c = Get_Raw_Char())) ret = ret * 10 + int(c - '0');
	if (neg) return -ret;
	return ret;
}

static inline long long int Get_Pll() {
	char c = Get_Raw_Char();
	long long int ret;
	while (!isdigit(c)) c = Get_Raw_Char();
	ret = int(c - '0');
	while (isdigit(c = Get_Raw_Char())) ret = ret * 10 + int(c - '0');
	return ret;
}

template <typename T> static inline void Read_P(T &n) {
	static_assert(is_integral<T>::value);
	char c = Get_Raw_Char();
	while (!isdigit(c)) c = Get_Raw_Char();
	n = int(c - '0');
	while (isdigit(c = Get_Raw_Char())) n = n * 10 + int(c - '0');
	return ;
}

template <typename T> static inline void Read(T &n) {
	static_assert(is_integral<T>::value);
	char c = Get_Raw_Char();
	bool neg = false;
	while (!isdigit(c)) {
		if (c == '-') neg = true;
		c = Get_Raw_Char();
	}
	n = int(c - '0');
	while (isdigit(c = Get_Raw_Char())) n = n * 10 + int(c - '0');
	if (neg) n = -n;
	return ;
}

template <typename T> static inline void Read_Digit(T &n) {
	static_assert(is_integral<T>::value);
	char c = Get_Raw_Char();
	while (!isdigit(c)) c = Get_Raw_Char();
	n = int(c - '0');
	return ;
}

template <typename T, typename... Targs> static inline void Read(T &n, Targs&... Fargs) {
	Read(n);
	return Read(Fargs...);
}

template <typename T, typename... Targs> static inline void Read_Digit(T &n, Targs&... Fargs) {
	Read_Digit(n);
	return Read_Digit(Fargs...);
}

template <typename T, typename... Targs> static inline void Read_P(T &n, Targs&... Fargs) {
	Read_P(n);
	return Read_P(Fargs...);
}
// End of C:\Users\ianli\Desktop\CP\template\Various\Fast_IO.cpp


int ans[kN], a[kN], cnt[kN], cntcnt[kSq], k[kN], l[kN], r[kN], t[kN], c[kN], p[kN], x[kN];
ll querys[kN];
set<int> big;

inline void Insert(int x) {
	if (cnt[x] < kSq) {
		cntcnt[cnt[x]++]--;
		if (cnt[x] >= kSq) big.insert(x);
		else cntcnt[cnt[x]]++;
	}
	else {
		cnt[x]++;
	}
	return ;
}

inline void Erase(int x) {
	if (cnt[x] < kSq) {
		cntcnt[cnt[x]--]--;
		cntcnt[cnt[x]]++;
	}
	else {
		cnt[x]--;
		if (cnt[x] < kSq) {
			big.erase(x);
			cntcnt[cnt[x]]++;	
		}
	}
	return ;
}

int Cal(int k) {
	//printf("cal %d\n", k);
	int ans = kInf; 
	vector<ll> vec; // cnt, ppl 
	vector<int> tmp;
	vec.reserve(kSq);
	tmp.reserve(int(big.size()));
	for (int i = 1; i < kSq; i++) if (cntcnt[i]) vec.PB(ll(i) << 20 | cntcnt[i]);
	for (int i : big) tmp.PB(cnt[i]);
	sort(tmp.begin(), tmp.end());
	for (int i : tmp) vec.PB(ll(i) << 20 | 1);

	//printf("vec\n");
	//for (pair<int, int> i : vec) printf("(%d, %d)\n", i.F, i.S);

	int sz = int(vec.size());
	for (int l = 0, r = 0, now = 0; r < sz; r++) {
		now += (vec[r] & 0xfffff);
		while (l <= r && now - (vec[l] & 0xfffff) >= k) now -= (vec[l++] & 0xfffff);
		if (now >= k) ans = min<int>(ans, (vec[r] >> 20) - (vec[l] >> 20));
	}

	if (ans == kInf) return -1;
	return ans;
}

int main() {
	//ios::sync_with_stdio(false);
	//cin.tie(0);
	//freopen("file_name", "r", stdin);
	//freopen("file_name", "w", stdout);
	//fstream input, output;
	//input.open("file_name", ios::in);
	//output.open("file_name", ios::out);
	int n, m;
	Read_P(n, m);
	for (int i = 1; i <= n; i++) Read_P(a[i]);

	auto Val = [](int a, int b, int c) -> ll {return ((a / kSq3N) << 6 | (b / kSq3N)) << 6 | (c / kSq3N);};

	int nt = 0, nq = 0;
	for (int i = 1; i <= m; i++) {
		//int type;
		//Read_Digit(type);
		if (Get_Digit() == 1) {
			nq++;
			Read_P(l[nq], r[nq], k[nq]);
			querys[nq] = Val(l[nq], r[nq], t[nq] = nt) << 20 | nq;
		}
		else {
			Read_P(p[nt], x[nt]);
			c[nt] = a[p[nt]];
			a[p[nt]] = x[nt];
			nt++;
		}
	}

	sort(querys + 1, querys + nq + 1);
	int nl = 1, nr = 0;

	for (int query = 1; query <= nq; query++) {
		int id = querys[query] & 0xfffff;
		while (nt < t[id]) {
			if (nl <= p[nt] && p[nt] <= nr) {
				Erase(a[p[nt]]);
				Insert(x[nt]);
			}
			a[p[nt]] = x[nt];
			nt++;
		}

		while (nr < r[id]) Insert(a[++nr]);
		while (nl > l[id]) Insert(a[--nl]);

		while (nt > t[id]) {
			nt--;
			if (nl <= p[nt] && p[nt] <= nr) {
				Erase(a[p[nt]]);
				Insert(c[nt]);
			}
			a[p[nt]] = c[nt];
		}

		while (nr > r[id]) Erase(a[nr--]);
		while (nl < l[id]) Erase(a[nl++]);

		ans[id] = Cal(k[id]);
	}

	for (int i = 1; i <= nq; i++) printf("%d\n", ans[i]);
	//input.close();
	//output.close();
}
// End of g.cpp
