//没时间写别的了
#include <bits/stdc++.h>
using namespace std;
const int N=5e5+5;
#define ll __int128
struct Splay
{
    int ch[N][2],fa[N],cnt[N],siz[N],rt,tot;ll val[N];
    inline void pushup(int p){siz[p]=siz[ch[p][0]]+siz[ch[p][1]]+cnt[p];}
    inline bool get(int x){return x==ch[fa[x]][1];}
    inline void rotate(int x)
    {
        int y=fa[x],z=fa[y];bool f=get(x);if(z) ch[z][get(y)]=x;
        ch[y][f]=ch[x][f^1];if(ch[x][f^1]) fa[ch[x][f^1]]=y;
        fa[y]=x,ch[x][f^1]=y,fa[x]=z;pushup(y),pushup(x);
    }
    void splay(int x,int gl=0)
    {
        for(int f=fa[x];f=fa[x],f!=gl;rotate(x))
            if(fa[f]!=gl) rotate(get(x)==get(f)?f:x);
        if(!gl) rt=x;
    }
    inline int newnode(ll v){++tot;cnt[tot]=siz[tot]=1,val[tot]=v;return tot;}
    void insert(ll v)
    {
        if(!rt){rt=newnode(v);pushup(rt);return;}
        int p=rt;while(val[p]!=v&&ch[p][v>val[p]]) p=ch[p][v>val[p]];
        if(val[p]==v){cnt[p]++,pushup(p),splay(p);return;}
        int nw=newnode(v);fa[nw]=p,ch[p][v>val[p]]=nw,splay(nw);
    }
    int find(ll v)
    {
        int p=rt,ansp=0;
        while(1)
        {
            if(val[p]==v) return p;
            if(val[p]>=v) 
            {
                if(!ansp) ansp=p;
                else if(val[ansp]>val[p]) ansp=p;
            }
            if(v<val[p]&&ch[p][0]){p=ch[p][0];continue;}
            if(v>val[p]&&ch[p][1]){p=ch[p][1];continue;}
            break;
        }return ansp;
    }
    int rk(ll v){int p=find(v);if(!p) return 0;splay(p); return siz[ch[p][1]]+cnt[p];}
    ll kth(int k)
    {
        int p=rt;
        while(1)
        {
            if(siz[ch[p][1]]>=k) p=ch[p][1];
            else if(siz[ch[p][1]]+cnt[p]<k) k-=siz[ch[p][1]]+cnt[p],p=ch[p][0];
            else return val[p];
        }
    }
}S;
int n,Q;ll a[N],k;long long tmp;
int p,nxp,rp,r[N];ll add,t;bool fl,ff;
int main()
{
    //freopen("bf.in","r",stdin);
    //freopen("bf.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);cin>>n>>Q>>tmp;k=tmp;
    for(int i=1;i<=n;i++) cin>>tmp,a[i]=tmp;
    sort(a+1,a+n+1,greater<int>()); 
    p=1,S.insert(a[1]);fl=(n>1?(a[2]-a[1])<k:0),rp=p+1;
    while(Q--)
    {
        char op;ll x;cin>>op>>tmp;x=tmp;
        if(op=='C')
        {
            t+=x;
            while(t>=p)
            {
                //cerr<<t<<" "<<p<<" "<<fl<<endl;
                if(!fl)
                {
                    ll M=S.kth(p),ti=t/p;
                    if(p<n) ti=min(ti,(M+add-a[p+1]-k)/k+1);
                    add-=ti*k,t-=ti*p;
                    if(p<n&&M+add-1ll*n*k-a[p+1]<k) fl=1,ff=0,rp=p+1;
                }
                else
                {
                    add-=k,t-=p;
                    if(!ff)
                    {
                        ll M=S.kth(p)+add;
                        nxp=p;while(nxp<n&&a[nxp+1]>=M) nxp++;
                    }
                    for(int i=rp;i<=nxp;i++) S.insert(a[i]-add);
                    p=nxp,nxp=0,rp=p+1;fl=(p<n?S.kth(p)+add-a[p+1]<k:0),ff=0;
                }
            }
            if(fl&&!ff)
            {
                ll M=S.kth(p)+add-k;ff=1;
                nxp=p;while(nxp<n&&a[nxp+1]>=M) nxp++;
                for(int i=p+1;i<=nxp;i++) 
                    r[i]=S.rk(a[i]-add+k)+1;
            }
        }
        else
        {
            ll res=0;
            if(!fl)
            {
                if(x>p) res=a[x];
                else res=S.kth(x+t>p?x+t-p:x+t)+add-(x+t>p?k:0);
            }
            else
            {
                if(x>nxp) res=a[x];
                else
                {
                    int y=upper_bound(r+p+1,r+nxp+1,t)-r-1;
                    if(x>y) res=a[x];
                    else 
                    {
                        while(rp<=y) S.insert(a[rp]-add+k),rp++;
                        int pos=x+y-p+t;
                        res=S.kth(pos>y?pos-y:pos)+add-(pos>y?k:0);
                    }
                }
            }cout<<(long long)res<<"\n";
        }
    }

    return 0;
}