// Exported by Exporter.exe

// 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], type[kN], a[kN], cnt[kN], cntcnt[kSq];
tuple<int, int, int> events[kN];
set<int> big;

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 ;
}

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, sz;
	vector<pair<int, int>> vec, tmp; // cnt, ppl 
	for (int i = 1; i < kSq; i++) if (cntcnt[i]) vec.PB(MP(i, cntcnt[i]));
	for (int i : big) tmp.PB(MP(cnt[i], 1));
	sort(tmp.begin(), tmp.end());
	for (pair<int, int> i : tmp) vec.PB(i);

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

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

	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;
	vector<tuple<int, int, int, int, int, int>> querys; // val, l, r, event, k, id
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++) scanf("%d", &a[i]);

	auto Val = [](int a, int b, int c) -> int {return ((a / kSq3N) * kSq3N + b / kSq3N) * kSq3N + c / kSq3N;};

	int nt = 0;
	for (int i = 1; i <= m; i++) {
		scanf("%d", &type[i]);
		if (type[i] == 1) {
			int l, r, k;
			scanf("%d%d%d", &l, &r, &k);
			querys.PB(MTP(Val(l, r, nt), l, r, nt, k, i));
		}
		else {
			int p, x;
			scanf("%d%d", &p, &x);
			events[nt++] = MTP(p, x, a[p]);
			a[p] = x;
		}
	}

	sort(querys.begin(), querys.end());
	memset(ans, 0x3f, sizeof(ans));
	int nl = 1, nr = 0;

	auto Change = [&](int p, int x) -> void {
		//printf("Change(%d, %d)\n", p, x);
		//for (int i = 1; i <= n; i++) printf("cnt[%d] = %d\n", i, cnt[i]);
		if (nl <= p && p <= nr) {
			Erase(a[p]);
			Insert(x);
		}
		//for (int i = 1; i <= n; i++) printf("cnt[%d] = %d\n", i, cnt[i]);
	};

	for (tuple<int, int, int, int, int, int> query : querys) {
		//printf("query = (%d, %d, %d)\n", get<1>(query), get<2>(query), get<3>(query));
		while (nt < get<3>(query)) {
			int p = get<0>(events[nt]), x = get<1>(events[nt]);
			Change(p, x);
			a[p] = x;
			nt++;
		}

		while (nr < get<2>(query)) Insert(a[++nr]);
		while (nl > get<1>(query)) Insert(a[--nl]);

		while (nt > get<3>(query)) {
			nt--;
			int p = get<0>(events[nt]), x = get<2>(events[nt]);
			Change(p, x);
			a[p] = x;
		}

		while (nr > get<2>(query)) Erase(a[nr--]);
		while (nl < get<1>(query)) Erase(a[nl++]);

		ans[get<5>(query)] = Cal(get<4>(query));
	}

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

