82pts卡不过求卡

#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cmath>
#define ll long long
#define re register
#define endl '\n'

using namespace std;
namespace ZYQIO{
	const int L=1<<20;
	inline char gc(){
	    static char buf[L],*l=buf,*r=buf;
	    if(l==r)r=(l=buf)+fread(buf,1,L,stdin);
	    return (l==r)?EOF:*l++;
	}
	char obuf[L],*p=obuf;
	inline void pc(char c){
	    if(p==obuf+L)
	        fwrite(obuf,1,L,stdout),p=obuf;
	    *p++=c;
	}
	inline void flush(){fwrite(obuf,1,p-obuf,stdout);}
	struct Reader{
	    template<typename T>
	    inline Reader& operator>>(T& x){
	        x=0;
	        short f=1;
	        char c=gc();
	        while(!isdigit(c)){
	            if(c=='-')
	                f=-1;
	            c=gc();
	        }
	        while(isdigit(c))x=10*x+(c-'0'),c=gc();
	        x*=f;
	        return *this;
	    }
	    Reader(){}
	}cin;
	struct Writer{
	    template<typename T>
	    inline Writer& operator<<(T x){
	        if(x < 0)pc('-'),x=-x;
	        static short tp=0,s[40];
	        do s[++tp]=x%10,x/=10;
	        while(x);
	        while(tp)pc(s[tp--] + '0');
	        return *this;
	    }
	    inline Writer& operator<<(const char* s){
	        int i=0;
	        while(s[i])pc(s[i++]);
	        return *this;
	    }
	    inline Writer& operator<<(char c){
	        pc(c);
	        return *this;
	    }
	    Writer(){}
	    ~Writer(){flush();}
	}cout;
}

#define cin ZYQIO::cin
#define cout ZYQIO::cout

// gotta go!

const int N = 1e5 + 9, M = 403, Blen = 403;

int a[N], B[N], L[N], R[N], len, lt[N], rt[N], cnt;
int sum1[M][M], sum2[M][N], n, q;
int pos[M][N], val[N], fa[N];

int temp1[N], temp2[N], temp[N];

inline int Find(int x) {
	return (fa[x] == x ? x : fa[x] = Find(fa[x]));
}
inline int getblock(int x) {
	return (x - 1) / Blen + 1;
}

inline void refac(int id) {
//	cout << id << endl;
	for (int i = L[id]; i <= R[id]; i ++)
		fa[i] = i, pos[id][a[i]] = 0, val[i] = 0;
	for (int i = L[id]; i <= R[id]; i ++) {
		if (pos[id][a[i]]){
			fa[i] = pos[id][a[i]];
		}else{
//			cout << "remind "<< i << endl;
			fa[i] = i;
			val[i] = a[i];
			pos[id][a[i]] = i;
		}
	}
}
// change and query part

inline void Change(int ql, int qr, int qx, int qy) {
	int bx = getblock(qx), by = getblock(qy);
	if (B[ql] == B[qr]) {
		int siz = 0;
		for (int i = lt[ql]; i <= rt[ql]; i ++){
			pos[B[ql]][a[i]] = 0;
			a[i] = val[Find(i)];
			pos[B[ql]][a[i]] = 0;
		}
		for (int i = ql; i <= qr; i ++){
			if (a[i] == qx) {
				siz ++;
				a[i] = qy;
			}
		}
		refac(B[ql]);
		
		for (int i = B[ql]; i <= cnt; i ++){
			sum1[i][bx] -= siz;
			sum1[i][by] += siz;
			sum2[i][qx] -= siz;
			sum2[i][qy] += siz;
		}
//		cout << "Change : " << endl;
//		for (int i = 1; i <= cnt; i ++, cout << endl)
//			for (int j = 1; j <= 10; j ++)
//				cout << sum2[i][j] << ' ';
//		cout << endl;
		
		return void();
	}
	
	//find the numbers of x for each segment
	
	for (int i = B[ql]; i <= cnt; i ++)
		temp[i] = 0;
	
	for (int i = lt[ql]; i <= rt[ql]; i ++) {
		pos[B[ql]][a[i]] = 0;
		a[i] = val[Find(i)];
		pos[B[ql]][a[i]] = 0;
		
		if (a[i] == qx && i >= ql) {
			a[i] = qy;
			temp[B[ql]] ++;
		}
	}
	
	
	for (int i = lt[qr]; i <= rt[qr]; i ++) {
		pos[B[qr]][a[i]] = 0;
		a[i] = val[Find(i)];
		pos[B[qr]][a[i]] = 0;
		
		if (a[i] == qx && i <= qr) {
			a[i] = qy;
			temp[B[qr]] ++;
		}
	}
	
	for (int i = B[ql] + 1; i <= cnt; i ++) {
		if (i < B[qr]) {
			temp[i] = sum2[i][qx] - sum2[i - 1][qx];	
			temp[i] += temp[i - 1];
		}else temp[i] += temp[i - 1];
	}
	//for each block, divide the temp[i]
	//for hole block, change its dsu
	
	for (int i = B[ql]; i <= cnt; i ++){
		sum1[i][bx] -= temp[i];
		sum1[i][by] += temp[i];
		sum2[i][qx] -= temp[i];
		sum2[i][qy] += temp[i];
	}
	for (int i = B[ql] + 1; i < B[qr]; i ++) {
		if (!pos[i][qx]) continue;
		if (!pos[i][qy]) {
			val[pos[i][qx]] = qy;
			pos[i][qy] = pos[i][qx];
			pos[i][qx] = 0;
			continue;
		}
		if (pos[i][qx] > pos[i][qy]) {
			fa[pos[i][qx]] = pos[i][qy];
			pos[i][qx] = 0;
		}else {
			fa[pos[i][qy]] = pos[i][qx];
			val[pos[i][qx]] = qy;
			pos[i][qy] = pos[i][qx];
			pos[i][qx] = 0;
		}
	}
	
	refac(B[ql]);
	refac(B[qr]);
	
//	cout << "Sum1 : " << endl;
//	for (int i = 1; i <= cnt; i ++, cout << endl) 
//		for(int j = 1; j <= 20; j ++)
//			cout << sum1[i][j] << ' ';
//	cout << "Sum2 : " << endl;
//	for (int i = 1; i <= cnt; i ++, cout << endl) 
//		for(int j = 1; j <= 20; j ++)
//			cout << sum2[i][j] << ' ';
//	cout << "Pos : " << endl;
//	for (int i = 1; i <= cnt; i ++, cout << endl)
//		for (int j = 1; j <= 20; j ++)
//			cout << pos[i][j] << ' ';
//	cout << endl;
//	cout <<"fa : " << endl;
//	for (int i = 1; i <= n; i ++)
//		cout << fa[i] << ' ';
//	cout << endl;
//	cout <<"val : " << endl;
//	for (int i = 1; i <= n; i ++)
//		cout << val[i] << ' ';
//	cout << endl;
	
	return void();
}

inline int Query(int ql, int qr, int qk) {
	if (B[ql] == B[qr]) {
		for (int i = ql; i <= qr; i ++) {
			a[i] = val[Find(i)];
//			cout << i << ' ' << a[i] << ' ' << Find(i) << endl;
			temp1[getblock(a[i])] ++;
			temp2[a[i]] ++;
		}
		
		int ans = 0, blockpos = 0;
		for (int i = 1; ; i ++) {
			if (temp1[i] >= qk) {
				blockpos = i;
				break;
			}else qk -= temp1[i];
		}
		for (int i = (blockpos - 1) * Blen + 1; ; i ++) {
			if (temp2[i] >= qk) {
				ans = i;
				break;
			}else qk -= temp2[i];
		}
	
		for (int i = ql; i <= qr; i ++) {
			temp1[getblock(a[i])] = 0;
			temp2[a[i]] = 0;
		}
		return ans;
	}
	
	for (int i = ql; i <= rt[ql]; i ++){
		a[i] = val[Find(i)];
		temp1[getblock(a[i])] ++;
		temp2[a[i]] ++;
	}
	for (int i = qr; i >= lt[qr]; i --){
		a[i] = val[Find(i)]; 
		temp1[getblock(a[i])] ++;
		temp2[a[i]] ++;
	}
	
	int ans = 0, blockpos = 1, sum = 0;
	for (int i = 1; ; i ++){
		sum = sum1[B[qr] - 1][i] - sum1[B[ql]][i];
		if (qk <= temp1[i] + sum){
			blockpos = i;
			break;
		}else qk -= (temp1[i] + sum);
	}
	for (int i = (blockpos - 1) * Blen + 1; ; i ++) {
		sum = sum2[B[qr] - 1][i] - sum2[B[ql]][i];
		if (qk <= temp2[i] + sum){
			ans = i;
			break;
		}else qk -= (temp2[i] + sum);
	}
	
	for (int i = ql; i <= rt[ql]; i ++){
		temp1[getblock(a[i])] = 0;
		temp2[a[i]] = 0;
	}
	for (int i = qr; i >= lt[qr]; i --){
		temp1[getblock(a[i])] = 0;
		temp2[a[i]] = 0;
	}
	
	return ans;
}

// init part
inline void init() {
	len = sqrt(n) + 1;
	
	for (int i = 1; i <= n; i ++) {
		if (i % len == 1){
			cnt ++;
			L[cnt] = i;
			R[cnt - 1] = i - 1;
		}
		B[i] = cnt;
		lt[i] = L[cnt];
	}
	R[cnt] = n;
	
	for (int i = 1; i <= n; i ++)
		rt[i] = R[B[i]];

	for (int i = 1; i <= cnt; i ++)
		refac(i);
		
//	for (int i = 1; i <= n; i ++)
//		cout << i << " : " << lt[i] << ' ' << rt[i] << endl;
}

int main() {
	
	cin >> n >> q;
	for (int i = 1; i <= n; i ++)
		cin >> a[i];
		
	init();
		
	for (int i = 1; i <= cnt; i ++) {
		for (int j = 1; j < M; j ++)
			sum1[i][j] = sum1[i - 1][j];
		for (int j = 1; j < N; j ++)
			sum2[i][j] = sum2[i - 1][j];

		for (int j = L[i]; j <= R[i]; j ++){
			sum1[i][getblock(a[j])] ++;
			sum2[i][a[j]] ++;
		}
	}
//	cout << "sum2 bef " << endl;
//	for (int i = 1; i <= cnt; i ++) {
//		cout << i << " : ";
//		for(int j = 1; j <= 300; j ++){
//			if (sum2[i][j]) {
//				cout << "(" << j << ", " << sum2[i][j] << "), ";
//			}
//		}
//		cout << endl;
//	}
//	cout << endl;
	
	int opt, ql, qr, qx, qy, qk;
	while (q --) {
		cin >> opt >> ql >> qr;
		if (opt == 1) {
			cin >> qx >> qy;
			if (qx == qy) continue;
			Change(ql, qr, qx, qy);
		}else {
			cin >> qk;
			cout << Query(ql, qr, qk) << endl;
		}
	}
	
	return 0;
}
/*
sum1:for each block, number block presum
sum2:for each block, specific number presum
lt: for each position, block left pos
rt: for each position, block right pos
L: for each block, left pos
R: for each block, right pos
*/