#include<bits/stdc++.h>
using namespace std;
inline long long read(){
    int w=0;long long x=0;char c=getchar();
    while(!isdigit(c)) w|=c=='-',c=getchar();
    while(isdigit(c)) x=x*10+c-'0',c=getchar();
    return w?-x:x;
}
namespace star
{
    const int maxn=5e5+10;
    inline char gc(){
        char c=getchar();
        while(isspace(c)) c=getchar();
        return c;
    }
    int n,m;
    long long k,a[maxn];
    #define ls son[ro][0]
    #define rs son[ro][1]
    int son[maxn][2],siz[maxn],tot,rnd[maxn],rt1,rt2;
    long long val[maxn];
    inline int newnode(long long a){
        val[++tot]=a,siz[tot]=1,rnd[tot]=rand();return tot;
    }
    inline void pushup(const int &ro){
        siz[ro]=siz[ls]+siz[rs]+1;
    }
    int merge(int a,int b){
        if(!a or !b) return a|b;
        if(rnd[a]<rnd[b]){
            son[a][1]=merge(son[a][1],b);
            pushup(a);return a;
        }else{
            son[b][0]=merge(a,son[b][0]);
            pushup(b);return b;
        }
    }
    void split(int ro,long long k,int &a,int &b){
        if(!ro) return a=b=0,void();
        if(val[ro]<=k) a=ro,split(rs,k,rs,b);
        else b=ro,split(ls,k,a,ls);
        pushup(ro);
    }
    inline void insert(int& rt,long long a){
        int x,y;
        split(rt,a,x,y);
        rt=merge(merge(x,newnode(a)),y);
    }
    void splitsz(int ro,int k,int &a,int &b){
        if(!ro) return a=b=0,void();
        if(siz[ls]+1<=k) a=ro,splitsz(rs,k-siz[ls]-1,rs,b);
        else b=ro,splitsz(ls,k,a,ls);
        pushup(ro);
    }
    inline long long kth(int ro,int a){
        while(true){
            // std::cerr << val[ro] << " ? " << std::endl;
            if(a<=siz[ls]) ro=ls;
            else{
                a-=siz[ls];
                if(--a==0) return val[ro];
                ro=rs;
            }
        }
    }
    #undef ls
    #undef rs
    long long s[maxn];
    inline void work(){
        n=read(),m=read(),k=read();
        for(int i=1;i<=n;i++) a[i]=read();
        sort(a+1,a+1+n);
        for(int i=n;i;i--) s[i]=s[i+1]+(n-i)*(a[i+1]/k-a[i]/k);
        long long h=a[n]/k,i=n;
        while(i and a[i]/k==h){
            h=a[i]/k;
            insert(rt1,a[i]%k);
            i--;
        }
        while(m--){
            // cerr<<"Before:"<<h<<' '<<siz[rt1]<<' '<<siz[rt2]<<endl;
            if(gc()=='C'){
            long long t=read();
            if(t>=siz[rt1]){
                t-=siz[rt1];
                rt1=merge(rt1,rt2);
                rt2=0;
                h--;
            }
            while(i and a[i]/k>=h-t/siz[rt1]){
                t-=(h-a[i]/k)*siz[rt1];
                h=a[i]/k;
                insert(rt1,a[i]%k);
                i--;
            }
            h-=t/siz[rt1];
            t-=(t/siz[rt1])*siz[rt1];
            if(t){
                int c;
                splitsz(rt1,siz[rt1]-t,rt1,c);
                rt2=merge(c,rt2);
                t=0;
                while(i and a[i]/k>=h-1){
                    insert(rt2,a[i]%k);
                    i--;
                }
            }
        }else{
            int x=read();
            if(x>siz[rt1]+siz[rt2]){
                printf("%lld\n",a[n-x+1]);
            }else if(x>siz[rt1]){
                // cerr<<"AAAAAAA:"<<h<<' '<<siz[rt1]<<' '<<siz[rt2]-(x-siz[rt1])+1<<endl;
                printf("%lld\n",k*(h-1)+kth(rt2,siz[rt2]-(x-siz[rt1])+1));
            }else printf("%lld\n",k*h+kth(rt1,siz[rt1]-x+1));
        }
            // cerr<<"After:"<<h<<' '<<siz[rt1]<<' '<<siz[rt2]<<endl<<endl;
        }
    }
}
signed main(){
    star::work();
    return 0;
}