写的是树状数组套线段树，就是两个log啊，但是就是T/kk

#include<bits/stdc++.h>
#define rep(i,a,b) for(R int i=a;i<=b;i++)
#define R register
#define endl putchar('\n')
const int N=5000005,inf=2147483647;
using namespace std;

int n,m,rt[N],sq[N],tot,a[N],tl[N],tr[N],cl,cr;
struct option {int op,l,r,k,ans;} q[N];

struct segment_tree {
	struct node {
		int ls,rs,sm;
		#define ls(x) nod[x].ls
		#define rs(x) nod[x].rs
		#define sm(x) nod[x].sm
	} nod[N<<4];
	int cnt;
	#define mid ((l+r)>>1)
	
	void add(int &k,int l,int r,int x,int v) {
		if(!k) k=++cnt;
		sm(k)+=v;
		if(l==r) return;
		if(x<=mid) add(ls(k),l,mid,x,v);
		else add(rs(k),mid+1,r,x,v);
	}
	int query(int k,int l,int r,int x,int y) {
		if(!k||x>y) return 0;
		if(x<=l&&r<=y) return sm(k);
		int res=0;
		if(x<=mid) res+=query(ls(k),l,mid,x,y);
		if(y>mid) res+=query(rs(k),mid+1,r,x,y);
		return res;
	}
	int query1(int l,int r,int k) {
		if(l==r) return sq[l];
		int sm=0;
		rep(i,1,cr) sm+=sm(ls(tr[i]));
		rep(i,1,cl) sm-=sm(ls(tl[i]));
		if(k<=sm) {
			rep(i,1,cr) tr[i]=ls(tr[i]);
			rep(i,1,cl) tl[i]=ls(tl[i]);
			return query1(l,mid,k);
		} else {
			rep(i,1,cr) tr[i]=rs(tr[i]);
			rep(i,1,cl) tl[i]=rs(tl[i]);
			return query1(mid+1,r,k-sm);
		}
	}
} smt;

#define lowbit(x) (x&-x)
int rank(int l,int r,int k) {
	int res=0;k=lower_bound(sq+1,sq+tot+1,k)-sq-1,l--;
	for(R int i=r;i>=1;i-=lowbit(i)) res+=smt.query(rt[i],1,tot,1,k);
	for(R int i=l;i>=1;i-=lowbit(i)) res-=smt.query(rt[i],1,tot,1,k);
	return res+1;
}
int find(int l,int r,int k) {
	for(R int i=r;i>=1;i-=lowbit(i)) tr[++cr]=rt[i];
	for(R int i=l-1;i>=1;i-=lowbit(i)) tl[++cl]=rt[i];
	return smt.query1(1,tot,k);
}
void modify(int p,int k) {
	for(R int i=p;i<=n;i+=lowbit(i)) smt.add(rt[i],1,tot,a[p],-1);
	a[p]=lower_bound(sq+1,sq+tot+1,k)-sq;
	for(R int i=p;i<=n;i+=lowbit(i)) smt.add(rt[i],1,tot,a[p],1);
}
int lower(int l,int r,int k) {
	k=rank(l,r,k);
	return k==1?-inf:find(l,r,k-1);
}
int upper(int l,int r,int k) {
	k=rank(l,r,k+1);
	return k==r-l+2?inf:find(l,r,k);
}

void init() {
	sort(sq+1,sq+tot+1);
	tot=unique(sq+1,sq+tot+1)-sq-1;
	rep(i,1,n) {
		a[i]=lower_bound(sq+1,sq+tot+1,a[i])-sq;
		for(R int j=i;j<=n;j+=lowbit(j)) smt.add(rt[j],1,tot,a[i],1);
	}
}

void solve() {
	rep(i,1,m) {
		switch(q[i].op) {
			case 1: printf("%d\n",rank(q[i].l,q[i].r,q[i].k)); break;
			case 2: printf("%d\n",find(q[i].l,q[i].r,q[i].k)); break;
			case 3: modify(q[i].l,q[i].k); break;
			case 4: printf("%d\n",lower(q[i].l,q[i].r,q[i].k)); break;
			case 5: printf("%d\n",upper(q[i].l,q[i].r,q[i].k)); break;
		}
	}
}

void file() {
	freopen("P3380_2.in","r",stdin);
	freopen("P3380.out","w",stdout);
}

int main() {
//	file();
	scanf("%d%d",&n,&m);
	rep(i,1,n) scanf("%d",&a[i]),sq[++tot]=a[i];
	rep(i,1,m) {
		scanf("%d",&q[i].op);
		if(q[i].op==3) {
			scanf("%d%d",&q[i].l,&q[i].k);
			sq[++tot]=q[i].k;
		} else scanf("%d%d%d",&q[i].l,&q[i].r,&q[i].k);
	}
	init();
	solve();
	return 0;
}