#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<cmath>
#include<algorithm>
using namespace std;
#define FILE "read"
#define MAXN 500010
#define INF 1000000000
//#define up(i,j,n) for(int i=j;i<=n;++i)
//#define dn(i,j,n) for(int i=j;i>=n;--i)
#define cmax(a,b) a=max(a,b)
#define cmin(a,b) a=min(a,b)
struct node{int x,y,k,cur,id,type;}q[MAXN],stack[MAXN][2];
int n,m,cnt,num,data[MAXN],ans[MAXN],tr[MAXN],temp[MAXN];
namespace INIT{
	char buf[1<<15],*fs,*ft;
	inline char getc(){return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++;}
	inline int read(){
		int x=0,f=1;  char ch=getchar();
		while(!isdigit(ch))  {if(ch=='-')  f=-1;  ch=getchar();}
		while(isdigit(ch))  {x=x*10+ch-'0';  ch=getchar();}
		return x*f;
	}
}using namespace INIT;
void add(int x,int v){while(x<=n)tr[x]+=v,x+=(x&-x);}
int get(int x){int sum(0);while(x)sum+=tr[x],x-=(x&-x);return sum;}
void init(){
	up(i,1,n)  data[i]=read(),q[++num]=(node){i,data[i],0,0,0,1};
	up(i,1,m){
		char ch[3]; scanf("%s",ch+1);
		if(ch[1]=='Q'){
			int x=read(),y=read(),k=read();
			q[++num]=(node){x,y,k,0,++cnt,3};
		}
		else{
			int x=read(),v=read();
			q[++num]=(node){x,data[x],0,0,0,2};
			q[++num]=(node){x,v,0,0,0,1};
			data[x]=v;
		}
	}
}
void solve(int l,int r,int L,int R){
	if(l>r)  return;
	if(L==R){
		up(i,l,r) if(q[i].type==3) ans[q[i].id]=L;
		return;
	}
	int mid=(L+R)>>1,ta(0),tb(0);
	up(i,l,r){
		if(q[i].y<=mid&&q[i].type==1) add(q[i].x,1);
		if(q[i].y<=mid&&q[i].type==2) add(q[i].x,-1);
		if(q[i].type==3)  temp[i]=get(q[i].y)-get(q[i].x-1);
	}
	up(i,l,r){
		if(q[i].y<=mid&&q[i].type==1) add(q[i].x,-1);
		if(q[i].y<=mid&&q[i].type==2) add(q[i].x,1);
	}
	up(i,l,r){
		if(q[i].type==3){
			if(q[i].cur+temp[i]>=q[i].k)  stack[++ta][0]=q[i];
			else q[i].cur+=temp[i],stack[++tb][1]=q[i];
		}
		else{
			if(q[i].y<=mid)  stack[++ta][0]=q[i];
			else stack[++tb][1]=q[i];
		}
	}
	up(i,1,ta)  q[i+l-1]=stack[i][0];
	up(i,1,tb)  q[i+l+ta-1]=stack[i][1];
	solve(l,l+ta-1,L,mid);
	solve(l+ta,r,mid+1,R);
}
void pre(){
	cnt=num=0;
}
int main(){
	freopen(FILE".in","r",stdin);
	freopen(FILE".out","w",stdout);
	while(~scanf("%d%d",&n,&m)){
		pre(); init();
		solve(1,num,0,INF);
		up(i,1,cnt)  printf("%d\n",ans[i]);
	}
	return 0;
}