先不管踢的，先看看怎么在#5#6#9挖的吧（

都是在比较后面挖的，本地 80 以内完全拍不出来。

#include<bits/stdc++.h>
#define ri register int
#define ll long long
using namespace std;
const int maxn=1e5+7;
int n,m;
int block_siz,num_siz;
int sum[500][maxn];
int sum_block[500][500];
int a[maxn];
int rt[500][maxn];// 位置为真位置
int f[500][500];// 位置为块内位置
int siz[500][500];
inline int find(int blk,int k){
	if(f[blk][k]==k)return k;
	f[blk][k]=find(blk,f[blk][k]);
	return f[blk][k];
}
int bl[maxn],br[maxn];
int belong[maxn];
int belong_num[maxn];
int bln[maxn],brn[maxn];
inline void merge(int blk,int a,int b){
	a=find(blk,a);
	b=find(blk,b);
	if(a==b)return;
	f[blk][a]=b;
	siz[blk][b]+=siz[blk][a];
}
void small_chg(int l,int r,int x,int y){
	if(belong[l]!=belong[r]){
		cout<<"寄\n";
		exit(0);
	}
	for(ri i=bl[belong[l]];i<=br[belong[r]];i++){
		a[i]=a[find(belong[l],i-bl[belong[l]]+1)+bl[belong[l]]-1];
	}
	rt[belong[l]][x]=rt[belong[l]][y]=0;
	for(ri i=bl[belong[l]];i<=br[belong[r]];i++){
		if(a[i]!=x&&a[i]!=y)continue;
		f[belong[l]][i-bl[belong[l]]+1]=i-bl[belong[l]]+1;
		siz[belong[l]][i-bl[belong[l]]+1]=1;
	}
	int cnt=0;
	for(ri i=bl[belong[l]];i<=br[belong[r]];i++){
		if(a[i]==x&&l<=i&&i<=r){
			cnt++;
			a[i]=y;
		}
		if(a[i]==x){
			if(!rt[belong[i]][x]){
				rt[belong[i]][x]=i;
			}
			else{
				merge(belong[i],i-bl[belong[i]]+1,rt[belong[i]][x]-bl[belong[i]]+1);
			}
		}
		if(a[i]==y){
			if(!rt[belong[i]][y]){
				rt[belong[i]][y]=i;
			}
			else{
				merge(belong[i],i-bl[belong[i]]+1,rt[belong[i]][y]-bl[belong[i]]+1);
			}
		}
	}
	for(ri i=belong[l];br[i];i++){
		sum[i][x]-=cnt;
		sum[i][y]+=cnt;
		sum_block[i][belong_num[x]]-=cnt;
		sum_block[i][belong_num[y]]+=cnt;
	}
}
inline int change_block(int blk,int x,int y){
	if(!rt[blk][x])return 0;
	if(!rt[blk][y]){
		rt[blk][y]=rt[blk][x];
		a[find(blk,rt[blk][x]-bl[blk]+1)+bl[blk]-1]=y;
		rt[blk][x]=0;
		return siz[blk][rt[blk][y]-bl[blk]+1];
	}
	int res=siz[blk][find(blk,rt[blk][x]-bl[blk]+1)];
	a[find(blk,rt[blk][x]-bl[blk]+1)+bl[blk]-1]=y;
	merge(blk,rt[blk][x]-bl[blk]+1,rt[blk][y]-bl[blk]+1);
	rt[blk][x]=0;
	return res;
}
void change(int l,int r,int x,int y){
	if(belong[l]==belong[r]){
		small_chg(l,r,x,y);
		return;
	}
	small_chg(l,br[belong[l]],x,y);
	int res=0;
	for(ri i=belong[l]+1;i<=belong[r]-1;i++){
		res+=change_block(i,x,y);
		sum[i][x]-=res;
		sum[i][y]+=res;
		sum_block[i][belong_num[x]]-=res;
		sum_block[i][belong_num[y]]+=res;
	}
	for(ri i=belong[r];br[i];i++){
		sum[i][x]-=res;
		sum[i][y]+=res;
		sum_block[i][belong_num[x]]-=res;
		sum_block[i][belong_num[y]]+=res;
	}
	small_chg(bl[belong[r]],r,x,y);
}
int tong[maxn];
int tong_block[500];
inline int query_small(int l,int r,int k){
	for(ri i=l;i<=r;i++){
		a[i]=a[find(belong[i],i-bl[belong[i]]+1)+bl[belong[i]]-1];
	}
	for(ri i=l;i<=r;i++){
		tong[a[i]]++;
		tong_block[belong_num[a[i]]]++;
	}
	int lst=0;
	int now_pos=1;
	while(lst+tong_block[now_pos]<k){
		lst+=tong_block[now_pos];
		now_pos++;
	}
	now_pos=bln[now_pos];
	while(lst+tong[now_pos]<k){
		lst+=tong[now_pos];
		now_pos++;
	}
	for(ri i=l;i<=r;i++){
		tong[a[i]]--;
		tong_block[belong_num[a[i]]]--;
	}
	return now_pos;
}
int maxi_num;
inline int query(int l,int r,int k){
	if(belong[l]==belong[r]){
		return query_small(l,r,k);
	}
	for(ri i=l;i<=br[belong[l]];i++){
		a[i]=a[find(belong[i],i-bl[belong[i]]+1)+bl[belong[i]]-1];
		tong[a[i]]++;
		tong_block[belong_num[a[i]]]++;
	}
	for(ri i=bl[belong[r]];i<=r;i++){
		a[i]=a[find(belong[i],i-bl[belong[i]]+1)+bl[belong[i]]-1];
		tong[a[i]]++;
		tong_block[belong_num[a[i]]]++;
	}
	int now_pos=1;
	int lst=0;
	while(lst+tong_block[now_pos]+sum_block[belong[r]-1][now_pos]-sum_block[belong[l]][now_pos]<k){
		lst+=tong_block[now_pos]+sum_block[belong[r]-1][now_pos]-sum_block[belong[l]][now_pos];
		now_pos++;
	}
	now_pos=bln[now_pos];
	while(lst+tong[now_pos]+sum[belong[r]-1][now_pos]-sum[belong[l]][now_pos]<k){
		lst+=tong[now_pos]+sum[belong[r]-1][now_pos]-sum[belong[l]][now_pos];
		now_pos++;
		assert(now_pos<=maxi_num);
	}
	for(ri i=l;i<=br[belong[l]];i++){
		tong[a[i]]--;
		tong_block[belong_num[a[i]]]--;
	}
	for(ri i=bl[belong[r]];i<=r;i++){
		tong[a[i]]--;
		tong_block[belong_num[a[i]]]--;
	}
	return now_pos;
}
void init(){
	block_siz=500;
	for(ri i=1;i<=n;i++){
		belong[i]=belong[max(0,i-block_siz)]+1;
	}
	memset(bl,0x3f,sizeof(bl));
	for(ri i=1;i<=n;i++){
		bl[belong[i]]=min(bl[belong[i]],i);
		br[belong[i]]=max(br[belong[i]],i);
	}
	num_siz=500;
	for(ri i=1;i<=maxi_num;i++){
		belong_num[i]=belong_num[max(0,i-num_siz)]+1;
	}
	memset(bln,0x3f,sizeof(bln));
	for(ri i=1;i<=maxi_num;i++){
		bln[belong_num[i]]=min(bln[belong_num[i]],i);
		brn[belong_num[i]]=max(brn[belong_num[i]],i);
	}
}
inline void build_block(int blk){
	for(ri i=bl[blk];i<=br[blk];i++){
		f[blk][i-bl[blk]+1]=i-bl[blk]+1;
		siz[blk][i-bl[blk]+1]=1;
	}
	for(ri i=bl[blk];i<=br[blk];i++){
		if(!rt[blk][a[i]]){
			rt[blk][a[i]]=i;
		}
		else{
			merge(blk,i-bl[blk]+1,rt[blk][a[i]]-bl[blk]+1);
		}
	}
	for(ri i=1;i<=br[blk];i++){
		sum[blk][a[i]]++;
		sum_block[blk][belong_num[a[i]]]++;
	}
}
inline int read(){
	int x=0;
	char c=getchar();
	while(c<'0'||c>'9'){
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		x=x*10+c-'0';
		c=getchar();
	}
	return x;
}
inline void write(ll x){
	if(x/10)write(x/10);
	putchar(x%10+'0');
}
signed main(){
	n=read();m=read();
	for(ri i=1;i<=n;i++){
		a[i]=read();
	}
	maxi_num=1e5;
	init();
	for(ri i=1;br[i];i++){
		build_block(i);
	}
	for(ri i=1;i<=m;i++){
		int op,l,r,k,x,y;
		op=read();
		l=read();
		r=read();
		if(op==1){
			x=read();
			y=read();
			change(l,r,x,y);
		}
		else{
			k=read();
			write(query(l,r,k));
			putchar('\n');
		}
	}
	return 0;
}