#include<bits/stdc++.h>//
#define int long long//
const int N=1e6+3;//
struct st{//
	int l,r,val,id,pd;//
}v1[N],v2[N],v3[N];//
int tr[N],n,m,a[N],l,r,x,s,ans[N];//
char opt[100];//
int lowbit(int x){//
	return x&(-x);//
}//
void update(int x,int y){//
	for(int i=1;i<=n;i+=lowbit(i))tr[i]+=y;//
}//
int query(int x){//
	int ans=0;//
	for(int i=x;i;i-=lowbit(i))ans+=tr[i];//
	return ans;//
}//
int solve(int l,int r){//
	return query(r)-query(l-1);//
}//
void sol(int l,int r,int L,int R){//
	if(L>R)return;//
	if(l==r){//
		for(int i=L;i<=R;i++)if(v1[i].pd==2)ans[v1[i].id]=l;//
		return;//
	}//
	int mid=(l+r)>>1,s1=0,s2=0;//
	for(int i=L;i<=R;i++){//
		if(v1[i].pd==1){//
			if(v1[i].l<=mid)v2[++s1]=v1[i],update(v1[i].id,v1[i].r);//
			else v3[++s2]=v1[i];//
		}//
		else{//
			int p=solve(v1[i].l,v1[i].r);//
			if(v1[i].val<=p)v2[++s1]=v1[i];//
			else v1[i].val-=p,v3[++s2]=v1[i];//
		}//
	}//
	for(int i=1;i<=s1;i++)if(v2[i].pd==1)update(v2[i].id,-v2[i].r);//
	for(int i=L,j=1;j<=s1;i++,j++)v1[i]=v2[j];//
	for(int i=L+s1,j=1;j<=s2;i++,j++)v1[i]=v3[j];//
//	printf("%lld %lld\n",s1,s2);//
	sol(l,mid,L,L+s1-1),sol(mid+1,r,L+s1,R);//
}//
signed main(){//
	scanf("%lld%lld",&n,&m);//
	for(int i=1;i<=n;i++)scanf("%lld",a+i),v1[++s]=(st){a[i],1,-1,i,1};//
	for(int i=1;i<=1000000;i++)ans[i]=1e9+3;//
	for(int i=1;i<=m;i++){//
		scanf("%s",opt+1);//
		if(opt[1]=='Q')scanf("%lld%lld%lld",&l,&r,&x),v1[++s]=(st){l,r,x,i,2};//
		else scanf("%lld%lld",&l,&r),v1[++s]=(st){a[l],-1,-1,l,1},a[l]=r,v1[++s]=(st){a[l],1,-1,l,1};//
	}//
//	puts("1");
//	printf("s=%lld\n",s);
	sol(-1e9,1e9,1,s);//
	for(int i=1;i<=m;i++)if(ans[i]<=1e9)printf("%lld\n",ans[i]);// 
	return 0;//
}//

rt，只过了hack