心态崩了 qwq。

#include<bits/stdc++.h>
#define lowbit(x) (x&-x)
using namespace std;
const int N=50005;
int qr() {
	int x=0;
	char c=getchar();
	while(!isdigit(c)) c=getchar();
	while(isdigit(c)) x=x*10+c-'0',c=getchar();
	return x;
}
struct node {int lc,rc,sum;}tr[N*400];
int tot=0,n,m,a[N],flag[N<<3],top,l[N],r[N],k[N],tmp[N],vec[2][25],tp[2];
void update(int &p,int x,int delta,int l,int r) {
	if(!p) p=++tot;
	tr[p].sum+=delta;
	if(l==r) return ;
	if((l+r>>1)>=x) update(tr[p].lc,x,delta,l,l+r>>1);
	else update(tr[p].rc,x,delta,(l+r>>1)+1,r);
}
int kth_toward(int k,int l,int r) {
	if(l==r) return l;
	int sum=0;
	for(int i=1;i<=tp[0];i++) sum+=tr[tr[vec[0][i]].lc].sum;
	for(int i=1;i<=tp[1];i++) sum-=tr[tr[vec[1][i]].lc].sum;
	if(k>sum) {
		for(int i=1;i<=tp[0];i++) vec[0][i]=tr[vec[0][i]].rc;
		for(int i=1;i<=tp[1];i++) vec[1][i]=tr[vec[1][i]].rc;
		return kth_toward(k-sum,(l+r>>1)+1,r);
	}
	for(int i=1;i<=tp[0];i++) vec[0][i]=tr[vec[0][i]].lc;
	for(int i=1;i<=tp[1];i++) vec[1][i]=tr[vec[1][i]].lc;
	return kth_toward(k,l,l+r>>1);
}
int kth_backward(int k,int l,int r) {
	if(l==r) return l;
	int sum=0;
	for(int i=1;i<=tp[0];i++) sum+=tr[tr[vec[0][i]].rc].sum;
	for(int i=1;i<=tp[1];i++) sum-=tr[tr[vec[1][i]].rc].sum;
	if(k>sum) {
		for(int i=1;i<=tp[0];i++) vec[0][i]=tr[vec[0][i]].lc;
		for(int i=1;i<=tp[1];i++) vec[1][i]=tr[vec[1][i]].lc;
		return kth_backward(k-sum,l,l+r>>1);
	}
	for(int i=1;i<=tp[0];i++) vec[0][i]=tr[vec[0][i]].rc;
	for(int i=1;i<=tp[1];i++) vec[1][i]=tr[vec[1][i]].rc;
	return kth_backward(k,(l+r>>1)+1,r);
}
int getsum_toward(int t,int l,int r) {
	int sum=0;
	if(r<=t) {
		for(int i=1;i<=tp[0];i++) sum+=tr[vec[0][i]].sum;
		for(int i=1;i<=tp[1];i++) sum-=tr[vec[1][i]].sum;
		return sum;
	}
	if(t>(l+r>>1)) {
		for(int i=1;i<=tp[0];i++) sum+=tr[tr[vec[0][i]].lc].sum;
		for(int i=1;i<=tp[1];i++) sum-=tr[tr[vec[1][i]].lc].sum;
		for(int i=1;i<=tp[0];i++) vec[0][i]=tr[vec[0][i]].rc;
		for(int i=1;i<=tp[1];i++) vec[1][i]=tr[vec[1][i]].rc;
		return sum+getsum_toward(t,(l+r>>1)+1,r);
	}
	for(int i=1;i<=tp[0];i++) vec[0][i]=tr[vec[0][i]].lc;
	for(int i=1;i<=tp[1];i++) vec[1][i]=tr[vec[1][i]].lc;
	return getsum_toward(t,l,l+r>>1);
}
int getsum_backward(int s,int l,int r) {
	int sum=0;
	if(s<=l) {
		for(int i=1;i<=tp[0];i++) sum+=tr[vec[0][i]].sum;
		for(int i=1;i<=tp[1];i++) sum-=tr[vec[1][i]].sum;
		return sum;
	}
	if(s<=(l+r>>1)) {
		for(int i=1;i<=tp[0];i++) sum+=tr[tr[vec[0][i]].rc].sum;
		for(int i=1;i<=tp[1];i++) sum-=tr[tr[vec[1][i]].rc].sum;
		for(int i=1;i<=tp[0];i++) vec[0][i]=tr[vec[0][i]].lc;
		for(int i=1;i<=tp[1];i++) vec[1][i]=tr[vec[1][i]].lc;
		return sum+getsum_backward(s,l,l+r>>1);
	}
	for(int i=1;i<=tp[0];i++) vec[0][i]=tr[vec[0][i]].rc;
	for(int i=1;i<=tp[1];i++) vec[1][i]=tr[vec[1][i]].rc;
	return getsum_backward(s,(l+r>>1)+1,r);
}
void add(int x,int p,int delta) {
	while(x<=n) update(x,p,delta,1,top),x+=lowbit(x);
}
int askk_toward(int l,int r,int k) {
	tp[0]=tp[1]=0,l--;
	while(r) vec[0][++tp[0]]=r,r-=lowbit(r);
	while(l) vec[1][++tp[1]]=l,l-=lowbit(l);
	return kth_toward(k,1,top);
}
int askk_backward(int l,int r,int k) {
	tp[0]=tp[1]=0,l--;
	while(r) vec[0][++tp[0]]=r,r-=lowbit(r);
	while(l) vec[1][++tp[1]]=l,l-=lowbit(l);
	return kth_backward(k,1,top);
}
int asks_toward(int l,int r,int k) {
	tp[0]=tp[1]=0,l--;
	while(r) vec[0][++tp[0]]=r,r-=lowbit(r);
	while(l) vec[1][++tp[1]]=l,l-=lowbit(l);
	return getsum_toward(k,1,top);
}
int asks_backward(int l,int r,int k) {
	tp[0]=tp[1]=0,l--;
	while(r) vec[0][++tp[0]]=r,r-=lowbit(r);
	while(l) vec[1][++tp[1]]=l,l-=lowbit(l);
	return getsum_backward(k,1,top);
}
int main() {
	n=qr(),m=qr();
	for(int i=1;i<=n;i++) {
		a[i]=qr();
		flag[++top]=a[i];
	}
	for(int i=1;i<=m;i++) {
		tmp[i]=qr();
		if(tmp[i]==1) l[i]=qr(),r[i]=qr(),flag[++top]=k[i]=qr();
		else if(tmp[i]==2) l[i]=qr(),r[i]=qr(),k[i]=qr();
		else if(tmp[i]==3) l[i]=qr(),flag[++top]=k[i]=qr();
		else if(tmp[i]==4) l[i]=qr(),r[i]=qr(),flag[++top]=k[i]=qr();
		else l[i]=qr(),r[i]=qr(),flag[++top]=k[i]=qr();
	}
	sort(flag+1,flag+top+1),top=unique(flag+1,flag+top+1)-flag-1;
	for(int i=1;i<=n;i++) tr[++tot]=(node){0,0,0};
	for(int i=1;i<=n;i++) a[i]=lower_bound(flag+1,flag+top+1,a[i])-flag,add(i,a[i],1);
	for(int i=1,cyy;i<=m;i++) {
//		puts("--------------------------------------------------------------------");
		if(tmp[i]!=2) k[i]=lower_bound(flag+1,flag+top+1,k[i])-flag;
//		cout << tmp[i] << " " << k[i] << " " << l[i] << " " << r[i] << ":\n";
//		for(int j=1;j<=n;j++) cout << a[j] << " ";
//		puts("");
		if(tmp[i]==1) {
			printf("%d\n",asks_toward(l[i],r[i],k[i]-1)+1);
		}else if(tmp[i]==2) {
			printf("%d\n",flag[askk_toward(l[i],r[i],k[i])]);
		}else if(tmp[i]==3) {
			add(l[i],a[l[i]],-1),add(l[i],k[i],1),a[l[i]]=k[i];
		}else if(tmp[i]==4) {
			cyy=asks_toward(l[i],r[i],k[i]-1);
			if(cyy==0) printf("-2147483647\n");
			else printf("%d\n",flag[askk_toward(l[i],r[i],cyy)]);
		}else {
			cyy=asks_backward(l[i],r[i],k[i]+1);
			if(cyy==0) printf("2147483647\n");
			else printf("%d\n",flag[askk_backward(l[i],r[i],cyy)]);
		}
	}
	return 0;
}