#include <bits/stdc++.h>
// #define int long long
#define min std::min
#define max std::max
#define swap std::swap
#ifndef ONLINE_JUDGE
bool online_judge = true;
#else
bool online_judge = false;
#endif

namespace IO
{
	const int N = 1e6 + 5;
	char obuf[N], * p3 = obuf; char ibuf[N], * p1 = ibuf, * p2 = ibuf;
	inline void flush() { fwrite(obuf, p3 - obuf, 1, stdout); p3 = obuf; }
	inline void putch(char x) { (p3 - obuf < N) ? (*p3++ = x) : (flush(), *p3++ = x); }
	inline char getch() { if (online_judge) return getchar(); else return p1 == p2 && (p2 = (p1 = ibuf) + fread(ibuf, 1, N, stdin), p1 == p2) ? EOF : *p1++; }
	inline bool Read(char* p) { char ch = getch(); while (ch == ' ' || ch == '\n' || ch == -1) { if (ch == -1) return true; ch = getch(); } while (ch != ' ' && ch != '\n' && ch != -1) { *p++ = ch; ch = getch(); } *p++ = '\0'; return ch == -1; }
	inline bool Read(std::string str) { str = ""; char ch = getch(); while (ch == ' ' || ch == '\n' || ch == -1) { if (ch == -1) return true; ch = getch(); } while (ch != ' ' && ch != '\n' && ch != -1) { str += ch; ch = getch(); } return ch == -1; }
	inline bool Read(signed& x) { register char ch = getch(); while (ch < '0' || ch > '9') { if (ch == -1) return true; if (ch == '-') { if (Read(x)) { x = -x; return true; } x = -x; return false; } ch = getch(); } x = 0; while (ch <= '9' && ch >= '0') { x = (x << 3) + (x << 1) + (ch ^ 48); ch = getch(); } if (ch == -1) return true; return false; }
	inline bool Read(short& x) { register char ch = getch(); while (ch < '0' || ch > '9') { if (ch == -1) return true; if (ch == '-') { if (Read(x)) { x = -x; return true; } x = -x; return false; } ch = getch(); } x = 0; while (ch <= '9' && ch >= '0') { x = (x << 3) + (x << 1) + (ch ^ 48); ch = getch(); } if (ch == -1) return true; return false; }
	inline bool Read(long long& x) { register char ch = getch(); while (ch < '0' || ch > '9') { if (ch == -1) return true; if (ch == '-') { if (Read(x)) { x = -x; return true; } x = -x; return false; } ch = getch(); } x = 0; while (ch <= '9' && ch >= '0') { x = (x << 3) + (x << 1) + (ch ^ 48); ch = getch(); } if (ch == -1) return true; return false; }
	inline bool Read(__int128_t& x) { register char ch = getch(); while (ch < '0' || ch > '9') { if (ch == -1) return true; if (ch == '-') { if (Read(x)) { x = -x; return true; } x = -x; return false; } ch = getch(); } x = 0; while (ch <= '9' && ch >= '0') { x = (x << 3) + (x << 1) + (ch ^ 48); ch = getch(); } if (ch == -1) return true; return false; }
	inline bool read() { return false; }
	template < typename T, typename ... T2 > inline bool read(T& x, T2& ... oth) { if (Read(x)) return true; return read(oth...); }
	inline void Write(char* ch) { register int len = strlen(ch); for (register int i = 0; i < len; i++) putch(ch[i]); }
	inline void Write(std::string ch) { register int siz = ch.size(); for (register int i = 0; i < siz; i++) putch(ch[i]); }
	inline void Write(signed& x) { if (!x) { putch('0'); return ; } register int len = 0; register signed k1 = x; register char c[50] = {}; if (k1 < 0) k1 = -k1, putch('-'); while (k1) c[len++] = k1 % 10 ^ 48, k1 /= 10; while (len--) putch(c[len]); }
	inline void Write(short& x) { if (!x) { putch('0'); return ; } register int len = 0; register short k1 = x; register char c[50] = {}; if (k1 < 0) k1 = -k1, putch('-'); while (k1) c[len++] = k1 % 10 ^ 48, k1 /= 10; while (len--) putch(c[len]); }
	inline void Write(long long& x) { if (!x) { putch('0'); return ; } register int len = 0; register long long k1 = x; register char c[50] = {}; if (k1 < 0) k1 = -k1, putch('-'); while (k1) c[len++] = k1 % 10 ^ 48, k1 /= 10; while (len--) putch(c[len]); }
	inline void Write(__int128_t& x) { if (!x) { putch('0'); return ; } register int len = 0; register __int128_t k1 = x; register char c[50] = {}; if (k1 < 0) k1 = -k1, putch('-'); while (k1) c[len++] = k1 % 10 ^ 48, k1 /= 10; while (len--) putch(c[len]); }
	inline void write() {  }
	template < typename T, typename ... T2 > inline void write(T x, T2 ... oth) { Write(x); write(oth...); }
}
using IO::read; using IO::write; using IO::flush; using IO::putch; using IO::getch;

const int N = 1e5 + 5, M = 320;
int n, m;
int a[N];
struct Kuai1
{
	int l, r, size, fa[M], value[M], repr[N];
    inline int Find(int x) { while (x != fa[x]) x = fa[x] = fa[fa[x]] = fa[fa[fa[x]]]; return x; }
	inline int find(int x) { return Find(x - l + 1); }
	inline void merge(int x, int y)
	{
		if (fa[repr[x]] != repr[x]) return ;
		if (!repr[y]) value[repr[x]] = y, repr[y] = repr[x], repr[x] = 0;
		else fa[repr[x]] = repr[y], value[x] = repr[x] = 0;
	}
// 	inline void init() { for (register int i = l; i <= r; i++) fa[i - l + 1] = i - l + 1, value[i - l + 1] = a[i], repr[a[i]] = i - l + 1; }
    inline void init()
	{
		for (register int i = l; i <= r; i++)
		{
		    if (repr[a[i]]) fa[repr[a[i]]] = i - l + 1, value[repr[a[i]]] = 0;
		    fa[i - l + 1] = i - l + 1, value[i - l + 1] = a[i], repr[a[i]] = i - l + 1;
		}
	}
};
Kuai1 k1[M];
int idx1, sq1, from1[N];
struct Kuai2
{
	int l, r, size;
};
Kuai2 k2[M];
int idx2, sq2, from2[N];
int op, l, r, x, y, sum, last, L, R;
int cnt1[M][M];
int cnt2[M][N];
int b[N];
int cnt[N], num;
int IIdx[N], iidx;
inline void pushdown(int x, int A, int B, int l, int r)
{
	for (register int i = k1[x].l; i <= k1[x].r; i++)
	{
		a[i] = k1[x].value[k1[x].find(i)];
		if (i >= l && i <= r && a[i] == A) a[i] = B;
	}
	k1[x].init();
}
inline void modify(int l, int r, int x, int y)
{
	L = from1[l], R = from1[r];
	sum = 0;
	for (register int i = l; i <= min(k1[L].r, r); i++)
	{
		if (k1[L].value[k1[L].find(i)] == x) sum++;
	}
	last = cnt2[L][x];
	cnt1[L][from2[x]] -= sum, cnt2[L][x] -= sum;
	cnt1[L][from2[y]] += sum, cnt2[L][y] += sum;
	pushdown(L, x, y, l, r);
	for (register int i = L + 1; i < R; i++)
	{
		sum += cnt2[i][x] - last;
		last = cnt2[i][x];
		cnt1[i][from2[x]] -= sum, cnt2[i][x] -= sum;
		cnt1[i][from2[y]] += sum, cnt2[i][y] += sum;
		k1[i].merge(x, y);
	}
	if (L != R) for (register int i = r; i >= max(k1[R].l, l); i--)
	{
		if (k1[R].value[k1[R].find(i)] == x) sum++;
	}
	if (L != R)
	{
	    cnt1[R][from2[x]] -= sum, cnt2[R][x] -= sum;
	    cnt1[R][from2[y]] += sum, cnt2[R][y] += sum;
	}
	for (register int j = R + 1; j <= idx1; j++)
	{
		cnt1[j][from2[x]] -= sum, cnt2[j][x] -= sum;
		cnt1[j][from2[y]] += sum, cnt2[j][y] += sum;
	}
	pushdown(R, x, y, l, r);
}
inline int get(int l, int r, int x)
{
	for (register int i = 1; i <= iidx; i++) cnt[IIdx[i]] = 0;
	iidx = num = 0;
	L = from1[l], R = from1[r];
	for (register int i = l; i <= min(k1[L].r, r); i++) { if (!cnt[from2[k1[L].value[k1[L].find(i)]]]) IIdx[++iidx] = from2[k1[L].value[k1[L].find(i)]]; cnt[from2[k1[L].value[k1[L].find(i)]]]++; }
	if (L != R) for (register int i = r; i >= max(k1[R].l, l); i--) { if (!cnt[from2[k1[R].value[k1[R].find(i)]]]) IIdx[++iidx] = from2[k1[R].value[k1[R].find(i)]]; cnt[from2[k1[R].value[k1[R].find(i)]]]++; }
	for (register int i = 1; i <= idx2; i++)
	{
		num += cnt[i] + max(0, cnt1[R - 1][i] - cnt1[L][i]);
		if (num >= x)
		{
			num -= cnt[i] + max(0, cnt1[R - 1][i] - cnt1[L][i]);
			for (register int i = 1; i <= iidx; i++) cnt[IIdx[i]] = 0;
			iidx = 0;
			for (register int i = l; i <= min(k1[L].r, r); i++) { if (!cnt[k1[L].value[k1[L].find(i)]]) IIdx[++iidx] = k1[L].value[k1[L].find(i)]; cnt[k1[L].value[k1[L].find(i)]]++; }
			if (L != R) for (register int i = r; i >= max(k1[R].l, l); i--) { if (!cnt[k1[R].value[k1[R].find(i)]]) IIdx[++iidx] = k1[R].value[k1[R].find(i)]; cnt[k1[R].value[k1[R].find(i)]]++; }
			for (register int j = k1[i].l; j <= k1[i].r; j++)
			{
				num += cnt[j] + max(0, cnt2[R - 1][j] - cnt2[L][j]);
				if (num >= x) return j;
			}
		}
	}
	return -1;
}
inline void solve()
{
	read(n, m);
	sq1 = sqrt(n);
	k1[1].l = 1, idx1 = 1;
	for (register int i = 1; i <= n; i++)
	{
		read(a[i]);
		k1[idx1].r = i, k1[idx1].size++;
		from1[i] = idx1;
		if (i % sq1 == 0)
		{
			k1[idx1].init();
			if (i != n) k1[++idx1].l = i + 1;
		}
	}
	if (n % sq1) k1[idx1].init();
	sq2 = sqrt(1e5);
	k2[1].l = 1, idx2 = 1;
	for (register int i = 1; i <= 1e5; i++)
	{
		k2[idx2].r = i, k2[idx2].size++;
		from2[i] = idx2;
		if (i % sq2 == 0 && i != 1e5) k2[++idx2].l = i + 1;
	}
	for (register int i = 1; i <= n; i++)
	{
		for (register int j = from1[i]; j <= idx1; j++)
		{
			cnt1[j][from2[a[i]]]++;
			cnt2[j][a[i]]++;
		}
	}
	while (m--)
	{
		read(op, l, r, x);
		if (op == 1)
		{
			read(y);
			modify(l, r, x, y);
		}
		if (op == 2)
		{
			write(get(l, r, x), "\n");
		}
	}
}
signed main()
{
	register int t = 1;
	// read(t);
	while (t--) solve();
	flush();
}