#include<bits/stdc++.h>
#define ls lc[i]
#define rs rc[i]
#define fi first
#define se second
#define min amin
#define max amax
#define eb emplace_back
using namespace std;
using ll=long long;
using LL=__int128;
using pii=pair<int,int>;
const int N=5E5+10;
const int inf=0x3f3f3f3f;
const int p=998244353;
template<typename T=int>T read(){T x;cin>>x;return x;}
template<typename U,typename V>U min(const U &x,const V &y){return x<y?x:y;}
template<typename U,typename V>U max(const U &x,const V &y){return y<x?x:y;}
template<typename U,typename ...V>U min(const U &x,const V &...y){return min(x,min(y...));}
template<typename U,typename ...V>U max(const U &x,const V &...y){return max(x,max(y...));}
template<typename U,typename V>bool cmin(U &x,const V &y){return y<x?x=y,true:false;}
template<typename U,typename V>bool cmax(U &x,const V &y){return x<y?x=y,true:false;}
template<typename U,typename ...V>bool cmin(U &x,const V &...y){return cmin(x,min(y...));}
template<typename U,typename ...V>bool cmax(U &x,const V &...y){return cmax(x,max(y...));}
template<typename T>T qpow(T x,int n){T y=1;for(;n;n>>=1,x*=x)if(n&1)y*=x;return y;}
ll sqrt_floor(const ll &x){ll l=0,r=INT_MAX;while(l+1^r){ll mid=l+r>>1;(x<mid*mid?r:l)=mid;}return l;}
ll sqrt_ceil(const ll &x){ll l=-1,r=INT_MAX;while(l+1^r){ll mid=l+r>>1;(mid*mid<x?l:r)=mid;}return r;}
istream &operator>>(istream &is,LL &x){string a;is>>a;bool k=a[0]=='-';if(k)a=a.substr(1);x=0;for(char &t:a)x=x*10+t-48;if(k)x=-x;return is;}
ostream &operator<<(ostream &os,LL x){if(x<0)os<<'-',x=-x;string a;do a+=x%10|48;while(x/=10);reverse(a.begin(),a.end());return os<<a;}
mt19937 rng(time(0));
struct mint{
    int x;
    mint():x(){}
    mint(const int &x):x(x<0?x+p:x){}
    mint inv()const{return qpow(*this,p-2);}
    mint operator-()const{return mint(x?p-x:x);}
    mint &operator+=(const mint &t){return (x+=t.x)<p?0:x-=p,*this;}
    mint &operator-=(const mint &t){return (x-=t.x)<0?x+=p:0,*this;}
    mint &operator*=(const mint &t){return x=ll(x)*t.x%p,*this;}
    mint &operator/=(const mint &t){return *this*=t.inv();}
    mint operator+(const mint &t)const{return mint(*this)+=t;}
    mint operator-(const mint &t)const{return mint(*this)-=t;}
    mint operator*(const mint &t)const{return mint(*this)*=t;}
    mint operator/(const mint &t)const{return mint(*this)/=t;}
    friend mint operator+(const int &x,const mint &y){return mint(x)+=y;}
    friend mint operator-(const int &x,const mint &y){return mint(x)-=y;}
    friend mint operator*(const int &x,const mint &y){return mint(x)*=y;}
    friend mint operator/(const int &x,const mint &y){return mint(x)/=y;}
    friend istream &operator>>(istream &is,mint &t){return is>>t.x;}
    friend ostream &operator<<(ostream &os,const mint &t){return os<<t.x;}
};

pair<ll,int>a[N];
ll c[N];
int rt[N],lc[N],rc[N],key[N],val[N],siz[N],pre[N],cnt;
int new_node(int w){
    int i=++cnt;
    key[i]=rng();
    val[i]=w;
    siz[i]=1;
    return i;
}
void split(int i,int &x,int &y,int k){
    if(!i)return x=y=0,void();
    int t=k-siz[rs]-1;
    if(t<0){
        x=i;
        siz[i]-=siz[rs];
        split(rs,rs,y,k);
        siz[i]+=siz[rs];
    }
    else{
        y=i;
        siz[i]-=siz[ls];
        split(ls,x,ls,t);
        siz[i]+=siz[ls];
    }
}
void split2(int i,int &x,int &y,int w){
    if(!i)return x=y=0,void();
    if(val[i]<w){
        x=i;
        siz[i]-=siz[rs];
        split2(rs,rs,y,w);
        siz[i]+=siz[rs];
    }
    else{
        y=i;
        siz[i]-=siz[ls];
        split2(ls,x,ls,w);
        siz[i]+=siz[ls];
    }
}
int mg(int x,int y){
    if(!x||!y)return x|y;
    if(key[x]<key[y]){
        siz[x]+=siz[y];
        rc[x]=mg(rc[x],y);
        return x;
    }
    siz[y]+=siz[x];
    lc[y]=mg(x,lc[y]);
    return y;
}
template<typename ...T>int mg(int x,T ...y){
    return mg(x,mg(y...));
}
int kth(int i,int k){
    while(1){
        int t=k-siz[ls]-1;
        if(!t)return val[i];
        if(t<0)i=ls;
        else{
            k=t;
            i=rs;
        }
    }
}
vector<int>q;
void dfs(int i){
    if(!i)return;
    dfs(ls);
    dfs(rs);
    ls=rs=0;
    siz[i]=1;
    q.eb(i);
}
int un(int x,int y){
    if(siz[x]<siz[y])swap(x,y);
    q.clear();
    dfs(y);
    int u,v;
    for(int &t:q){
        split2(x,u,v,val[t]);
        x=mg(u,t,v);
    }
    return x;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m,k;
    cin>>n>>m>>k;
    for(int i=1;i<=n;++i){
        ll x;
        cin>>x;
        a[i].fi=x/k;
        a[i].se=x%k;
    }
    sort(a+1,a+n+1);
    a[0].fi=-1;
    int s=0;
    for(int i=1;i<=n;++i){
        if(a[i].fi^a[i-1].fi){
            c[++s]=a[i].fi;
            pre[s]=pre[s-1];
        }
        rt[s]=mg(rt[s],new_node(a[i].se));
        ++pre[s];
    }
    while(m--){
        char op;
        ll x;
        cin>>op>>x;
        if(op=='A'){
            x=n-x+1;
            int i=lower_bound(pre+1,pre+s+1,x)-pre;
            cout<<c[i]*k+kth(rt[i],x-pre[i-1])<<'\n';
        }
        else{
            while(x){
                if(s>1&&x/siz[rt[s]]>=c[s]-c[s-1]){
                    x-=(c[s]-c[s-1])*siz[rt[s]];
                    --s;
                    rt[s]=un(rt[s],rt[s+1]);
                    pre[s]=pre[s+1];
                }
                else{
                    ll t=x/siz[rt[s]];
                    c[s]-=t;
                    x-=t*siz[rt[s]];
                    if(!x)break;
                    int u,v;
                    split(rt[s],u,v,x);
                    if(s>1&&c[s]==c[s-1]+1){
                        pre[s-1]+=siz[v];
                        rt[s-1]=mg(rt[s-1],v);
                        rt[s]=u;
                    }
                    else{
                        rt[s]=v;
                        rt[s+1]=u;
                        c[s+1]=c[s];
                        pre[s+1]=pre[s];
                        --c[s];
                        pre[s]-=siz[u];
                        ++s;
                    }
                    x=0;
                }
            }
        }
    }
    return 0;
}