#include<algorithm> #include<iostream> #include<cstdlib> #include<cstdio> #define N 2200001 using namespace std; int n,m,tot,top,sz; struct data{ int l,r,sum; }node[N]; int v[N],hash[N]; int A[N],B[N],K[N],root[N],sum[N],L[30],R[30],num[N],a,b,cnt; bool flag[N]; int lowbit(int x) {return x&(-x);} char s[3]; int find(int x) { int l=1,r=tot,mid; while(l<=r) { int mid=(l+r)>>1; if(hash[mid]<x)l=mid+1; else r=mid-1; } return l; } inline int read(){ int x=0;char ch=getchar(); while(ch<'0'||ch>'9')ch=getchar(); while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x; } void update(int pre,int &k,int l,int r,int v,int x){ k=++cnt; node[k].sum=node[pre].sum+x; if(l==r)return; node[k].l=node[pre].l;node[k].r=node[pre].r; int mid=(l+r)>>1; if(v<=mid)update(node[pre].l,node[k].l,l,mid,v,x); else update(node[pre].r,node[k].r,mid+1,r,v,x); } int query(int l,int r,int k){ if(l==r) return l; int i,suml=0,sumr=0; for(i=1;i<=a;i++) suml+=node[node[L[i]].l].sum; for(i=1;i<=b;i++) sumr+=node[node[R[i]].l].sum; int mid=(l+r)>>1; if(sumr-suml>=k) { for(i=1;i<=a;i++) L[i]=node[L[i]].l; for(i=1;i<=b;i++) R[i]=node[R[i]].l; return query(l,mid,k); } else { for(i=1;i<=a;i++) L[i]=node[L[i]].r; for(i=1;i<=b;i++) R[i]=node[R[i]].r; return query(mid+1,r,k-(sumr-suml)); } } int main(){ n=read();m=read(); for(int i=1;i<=n;i++){ v[i]=read(); num[++top]=v[i]; } for(int i=1;i<=m;i++){ scanf("%s",s); A[i]=read();B[i]=read(); if(s[0]=='Q')K[i]=read(),flag[i]=1; else num[++top]=B[i]; } sort(num+1,num+top+1); hash[++tot]=num[1]; for(int i=1;i<=top;i++) if(num[i]!=num[i-1]) hash[++tot]=num[i]; for(int i=1;i<=n;i++){ int t=find(v[i]); for(int j=i;j<=n;j+=lowbit(j)) update(root[j],root[j],1,tot,t,1); } for(int i=1;i<=m;i++) if(flag[i]){ a=0;b=0;A[i]--; for(int j=A[i];j>0;j-=lowbit(j)) L[++a]=root[j]; for(int j=B[i];j>0;j-=lowbit(j)) R[++b]=root[j]; printf("%d\n",hash[query(1,tot,K[i])]); } else{ int t=find(v[A[i]]); for(int j=A[i];j<=n;j+=lowbit(j)) update(root[j],root[j],1,tot,t,-1); v[A[i]]=B[i]; t=find(B[i]); for(int j=A[i];j<=n;j+=lowbit(j)) update(root[j],root[j],1,tot,t,1); } return 0; }