::::info[Code]

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define inf INT_MAX
using namespace std;
using namespace __gnu_pbds;
typedef tree<int,null_type,less_equal<int>,rb_tree_tag,tree_order_statistics_node_update> Otree;
int n,m,a[100004],cnt;
struct St{
#define ls tr[u].lc
#define rs tr[u].rc
#define mid ((l+r)>>1)
	struct Node{
		Otree Tr;
		int lc,rc;
	};
	vector<Node>tr;
	void init(int n){
		tr.resize(4*n+1);
		int rt=0;
		build(rt,1,n);
	}
	void build(int &u,int l,int r){
		if(!u) u=++cnt;
		tr[u].Tr.insert(inf),tr[u].Tr.insert(-inf);
		for(int i=l;i<=r;i++) tr[u].Tr.insert(a[i]);
		if(l==r) return;
		build(ls,l,mid);
		build(rs,mid+1,r);
	}
	int Rnk(int u,int l,int r,int ql,int qr,int val){
		if(ql<=l&&r<=qr){
			return tr[u].Tr.order_of_key(val)-1;
		}
		int res=0;
		if(mid>=ql) res+=Rnk(ls,l,mid,ql,qr,val);
		if(mid<qr) res+=Rnk(rs,mid+1,r,ql,qr,val);
		return res;
	}
	void update(int u,int l,int r,int pos,int val){
		tr[u].Tr.erase(tr[u].Tr.upper_bound(a[pos]));
		tr[u].Tr.insert(val);
		if(l==r){
			a[pos]=val;
			return;
		}
		if(mid>=pos) update(ls,l,mid,pos,val);
		else update(rs,mid+1,r,pos,val);
	}
	int Pre(int u,int l,int r,int ql,int qr,int val){
		if(ql<=l&&r<=qr){
			return *--tr[u].Tr.upper_bound(val);
		}
		int res=-inf;
		if(mid>=ql) res=max(Pre(ls,l,mid,ql,qr,val),res);
		if(mid<qr) res=max(Pre(rs,mid+1,r,ql,qr,val),res);
		return res;
	}
	int Nxt(int u,int l,int r,int ql,int qr,int val){
		if(ql<=l&&r<=qr){
			auto it=tr[u].Tr.lower_bound(val);
			return *it;
		}
		int res=inf;
		if(mid>=ql) res=min(Nxt(ls,l,mid,ql,qr,val),res);
		if(mid<qr) res=min(Nxt(rs,mid+1,r,ql,qr,val),res);
		return res;
	}
	int Kth(int ql,int qr,int k){
		int l=0,r=1e9+1,ans;
		while(l<=r){
			int Mid=(l+r)>>1;
			if(Rnk(1,1,n,ql,qr,Mid)+1<k) l=Mid+1,ans=Mid;
			else r=Mid-1;
		}
		return ans;
	}
}st;
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
//	freopen("data.in","r",stdin);
//	freopen("data.out","w",stdout);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	st.init(n);
	for(int i=1;i<=m;i++){
		char op;int l,r,k;cin>>op>>l>>r;
		if(op==1) cin>>k,cout<<st.Rnk(1,1,n,l,r,k)+1<<'\n';
		if(op=='Q') cin>>k,cout<<st.Kth(l,r,k+1)<<'\n';
		if(op=='C') st.update(1,1,n,l,r);
		if(op==4) cin>>k,cout<<st.Pre(1,1,n,l,r,k)<<'\n';
		if(op==5) cin>>k,cout<<st.Nxt(1,1,n,l,r,k)<<'\n';
	}
	return 0;
}

::::