#include<string.h>

 #include<stdlib.h>

 #include<stdio.h>

 //#include<assert.h>

 #include<algorithm>

 //#include<iostream>

 using namespace std;

 int n,m;

 #define maxn 30011

 const int inf=0x3f3f3f3f;

 struct Ope

 {

     int x,y,z,id,type;

     //type=1: 询问区间[x,y]第z大，询问编号id

     //type=0：把位置x的数修改为y，增加：z=1，删除：z=-1

 }q[maxn],al[maxn],ar[maxn];int len;

 int ans[maxn];

 struct BIT

 {

     int a[maxn];

     void add(int x,int v) {for (;x<=n;x+=x&-x) a[x]+=v;}

     int query(int x) {int ans=; for (;x;x-=x&-x) ans+=a[x]; return ans;}

 }t;

 void solve(int L,int R,int ql,int qr)

 {

     if (L>R || ql>qr) return;

     if (L==R)

     {

         for (int i=ql;i<=qr;i++) if (q[i].type) ans[q[i].id]=L;

         return;

     }

     int mid=(L+R)>>,lql=,lqr=;

     for (int i=ql;i<=qr;i++)

     {

         if (q[i].type)

         {

             int tmp=t.query(q[i].y)-t.query(q[i].x-);

             if (tmp>=q[i].z) al[++lql]=q[i];

             else

             {

                 q[i].z-=tmp;

                 ar[++lqr]=q[i];

             }

         }

         else

         {

             if (q[i].y<=mid)

             {

                 t.add(q[i].x,q[i].z);

                 al[++lql]=q[i];

             }

             else ar[++lqr]=q[i];

         }

     }

     for (int i=;i<=lql;i++) if (al[i].type==) t.add(al[i].x,-al[i].z);

     for (int i=,j=ql;i<=lql;i++,j++) q[j]=al[i];

     for (int i=,j=ql+lql;i<=lqr;i++,j++) q[j]=ar[i];

     solve(L,mid,ql,ql+lql-);

     solve(mid+,R,ql+lql,qr);

 }

 int a[maxn];

 int main()

 {

     scanf("%d%d",&n,&m);

     for (int i=;i<=n;i++) scanf("%d",&q[i].y),a[i]=q[i].y,q[i].x=i,q[i].z=,q[i].type=;

     char s[];

     int cntq=;

     for (int i=,j=n+;i<=m;i++,j++)

     {

         scanf("%s",s);

         if (s[]=='Q') scanf("%d%d%d",&q[j].x,&q[j].y,&q[j].z),q[j].id=++cntq,q[j].type=;

         else scanf("%d%d",&q[j].x,&q[j].y),q[j].z=,q[j].type=,

         q[j+]=(Ope){q[j].x,a[q[j].x],-,,},a[q[j].x]=q[j].y,j++;

         if (i==m) len=j;

     }

     solve(,inf,,len);

     for (int i=;i<=cntq;i++) printf("%d\n",ans[i]);

     return ;

 }