#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define x first 
#define y second
#define pb push_back
inline ll read() {
    char ch=getchar();
    ll res=0;
    while(!isdigit(ch)) ch=getchar();
    while(isdigit(ch)) res=res*10+(ch-'0'),ch=getchar();
    return res;
}
const int N=500010;
int n,m;
ll k;

int CNT,rt[N];//CNT 是根的编号计数器，RT[I]表示编号是I的线段树的根节点编号
int s[N]; // sz 的前缀和
ll val[N]; //val 是 a[i]/k 的值，下标是 a[i]%k

int sz[N*35];
int ls[N*35],rs[N*35];
//值域线段树，在本题中的信息就SZ,ls(lson),rs(rson)

int idx,stk[N],top;//IDX是节点编号（动态开点），STK[] TOP是回收点用的
inline int New() {
    if(top) return stk[top--];
    else 
        return ++idx; 
}
inline void modify(int &u,ll l,ll r,ll pos,int v) {
    if(!u) u=New();
    if(l==r) {sz[u]+=v; return;}
    ll mid=l+r>>1;
    if(pos<=mid) modify(ls[u],l,mid,pos,v);
    else modify(rs[u],mid+1,r,pos,v);
    sz[u]=0;
    if(ls[u]) sz[u]+=sz[ls[u]];
    if(rs[u]) sz[u]+=sz[rs[u]];
}//把左右边界是[l,r]的节点U的POS位置增加V
inline void split(int x,int &y,int k) {
    if(!x) return;
    y=New();
    if(k>sz[ls[x]]) split(rs[x],rs[y],k-sz[ls[x]]);
    else if(k==sz[ls[x]]) rs[y]=rs[x],rs[x]=0;
    else rs[y]=rs[x],rs[x]=0,split(ls[x],ls[y],k);//k<sz[ls[x]]
    sz[y]=sz[x]-k; sz[x]=k;
}//split(x,y,k)表示把线段树X中排名>K的部分分裂给Y
inline void del(int x) {
    stk[++top]=x;
    ls[x]=rs[x]=sz[x]=0;
}
inline int merge(int x,int y) {
    if(!x||!y) return x+y;
    sz[x]+=sz[y];
    ls[x]=merge(ls[x],ls[y]); 
    rs[x]=merge(rs[x],rs[y]);
    del(y);
    return x;
}
inline ll kth(int u,ll l,ll r,int k) {
    if(l==r) return l;
    int mid=l+r>>1;
    if(sz[ls[u]]<k) return kth(rs[u],mid+1,r,k-sz[ls[u]]);
    else return kth(ls[u],l,mid,k);
}//查询左右边界是[l,r]的节点U里排名是第K小的元素的值
ll a[N];
signed main() {
    // freopen("in.in","r",stdin);
    val[0]=-((ll)(1e18)+10);
    n=read(),m=read(),k=read();

    for(int i=1;i<=n;i++) a[i]=read();
    sort(a+1,a+n+1); 
    ll last=-1;
    for(int i=1;i<=n;i++) {
        ll now=a[i]/k;
        if(now==last) s[CNT]++,modify(rt[CNT],0,k-1,a[i]%k,1);
        else {
            CNT++;
            val[CNT]=now;
            s[CNT]=s[CNT-1]+1,modify(rt[CNT],0,k-1,a[i]%k,1);
            last=now;
        }
    }
    while(m--) {
        char op[3]; scanf("%s",op);
        ll x=read();
        if(op[0]=='C') {
            while(x) {
                if(x<sz[rt[CNT]]) {
                    int new_rt; split(rt[CNT],new_rt,sz[rt[CNT]]-x);
                    if(val[CNT]-1>val[CNT-1]) {
                        rt[CNT+1]=rt[CNT], val[CNT+1]=val[CNT], s[CNT+1]=s[CNT];
                        rt[CNT]=new_rt, val[CNT]--, s[CNT]=s[CNT-1]+x;
                        CNT++;
                    } // 一个新树
                    else {
                        s[CNT-1]+=x;
                        rt[CNT-1]=merge(rt[CNT-1],new_rt);
                    } // 和本来更小的一个合并
                    x=0;
                }   
                else {
                    ll t=x/sz[rt[CNT]];
                    if(t>=val[CNT]-val[CNT-1]) {
                        t=val[CNT]-val[CNT-1];
                        x-=t*sz[rt[CNT]];
                        
                        rt[CNT-1]=merge(rt[CNT-1],rt[CNT]);
                        s[CNT-1]=s[CNT];
                        CNT--;
                    } // 和下一级合并
                    else {
                        x-=t*sz[rt[CNT]];
                        val[CNT]-=t;
                    }// 直接减
                }
            }
        }
        else {
            x=n-x+1;
            int l=1,r=CNT;
            while(l<r) {
                int mid=(l+r)>>1;
                if(s[mid]>=x) r=mid;
                else l=mid+1;
            } // 找到第一个前缀和>=x 的块,确定第 x 个在哪颗树里
            x-=s[l-1];
            assert(x>0&&x<sz[rt[l]]);
            printf("%lld\n",val[l]*k+kth(rt[l],0,k-1,x));
        }
    }
    return 0;
}