#include<bits/stdc++.h>
using namespace std;
const int maxn=5e5+10;
const long long lim=1e18;
int n,m;
long long a[maxn];
int RT1;
namespace SegmentTree1
{

    int tot=0;
    int son[maxn*60][2];
    int sum[maxn*60];
    long long query(int rt,long long l,long long r)
    {
        if(l==r)return l;
        long long mid=l+r>>1;
        if(sum[son[rt][1]])return query(son[rt][1],mid+1,r);
        else return query(son[rt][0],l,mid);
    }
    pair<long long,int> ask(int rt,long long l,long long r,int x)
    {
        if(l==r)return {l,x};
        long long mid=l+r>>1;
        if(sum[son[rt][1]]<x)return ask(son[rt][0],l,mid,x-sum[son[rt][1]]);
        else return ask(son[rt][1],mid+1,r,x);
    }
    void update(int &rt,long long l,long long r,long long p,long long v)
    {
        if(!rt)rt=++tot;
        if(l==r)
        {
            sum[rt]+=v;
            return;
        }
        long long mid=l+r>>1;
        if(p<=mid)update(son[rt][0],l,mid,p,v);
        else update(son[rt][1],mid+1,r,p,v);
        sum[rt]=sum[son[rt][0]]+sum[son[rt][1]];
    }
}
namespace SegmentTree2
{
    int tot=0;
    int son[maxn*20][2];
    int sum[maxn*20];
    int merge(int x,int y)
    {
        if(!x||!y) return x+y;
        sum[x]=sum[x]+sum[y];
        son[x][0]=merge(son[x][0],son[y][0]);
        son[x][1]=merge(son[x][1],son[y][1]);
        return x;
    }
    void split(int x,int &y,long long l,long long r,long long L)
    {
        if(!x)return;
        y=++tot;
        if(l==r)
        {
            sum[y]=L;
            sum[x]-=L;
            return;
        }
        long long mid=l+r>>1;
        if(sum[son[x][1]]<L)
        {
            son[y][1]=son[x][1];
            son[x][1]=0;
            split(son[x][0],son[y][0],l,mid,L-sum[son[y][1]]);
        }
        else if(sum[son[x][1]]==L)
        {
            son[y][1]=son[x][1];
            son[x][1]=0;
        }
        else split(son[x][1],son[y][1],mid+1,r,L);
        sum[y]=sum[son[y][0]]+sum[son[y][1]];
        sum[x]=sum[son[x][0]]+sum[son[x][1]];
    }
    void update(int &rt,long long l,long long r,long long p,long long v)
    {
        if(!rt)rt=++tot;
        if(l==r)
        {
            sum[rt]+=v;
            return;
        }
        long long mid=l+r>>1;
        if(p<=mid)update(son[rt][0],l,mid,p,v);
        else update(son[rt][1],mid+1,r,p,v);
        sum[rt]=sum[son[rt][0]]+sum[son[rt][1]];
    }
    long long ask(int rt,long long l,long long r,int x)
    {
        if(l==r)return l;
        long long mid=l+r>>1;
        if(sum[son[rt][1]]<x)return ask(son[rt][0],l,mid,x-sum[son[rt][1]]);
        else return ask(son[rt][1],mid+1,r,x);
    }
}
map<long long,int>Rt;
long long k;
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(0);
    cin>>n>>m;
    cin>>k;
    vector<long long>vec;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        vec.push_back(a[i]%k);
    }
    sort(vec.begin(),vec.end());
    vec.erase(unique(vec.begin(),vec.end()),vec.end());
    int lim=vec.size();
    for(int i=1;i<=n;i++)
    {
        SegmentTree1::update(RT1,-lim,lim,a[i]/k,1);
        int t=lower_bound(vec.begin(),vec.end(),a[i]%k)-vec.begin();
        SegmentTree2::update(Rt[a[i]/k],0,lim,t,1);
    }
    while(m--)
    {
        string op;
        cin>>op;
        if(op[0]=='A')
        {
            int x;
            cin>>x;
            pair<long long,int> p1=SegmentTree1::ask(RT1,-lim,lim,x);
           
            long long p2=SegmentTree2::ask(Rt[p1.first],0,lim,p1.second);
            cout<<p1.first*k+vec[p2]<<'\n';
        }
        else 
        {
            long long x;
            cin>>x;
            long long p;
            long long np=SegmentTree1::query(RT1,-lim,lim);
            while(1)
            {
                p=np;
                int tot=SegmentTree2::sum[Rt[p]];
                if(x>=tot)
                {
                    SegmentTree1::update(RT1,-lim,lim,p,-tot);
                    if(tot==n)
                    {
                        long long cnt=x/tot;
                        np=p-cnt;
                    }
                    else np=SegmentTree1::query(RT1,-lim,lim);
                    if((p-np)*tot<=x)
                    {
                        x-=(p-np)*tot;
                        Rt[np]=SegmentTree2::merge(Rt[np],Rt[p]);
                        SegmentTree1::update(RT1,-lim,lim,np,tot);
                    }
                    else 
                    {
                        long long cnt=x/tot;
                        x%=tot;
                        np=p-cnt;
                        Rt[np]=SegmentTree2::merge(Rt[np],Rt[p]);
                        SegmentTree1::update(RT1,-lim,lim,np,tot);
                    }
                }
                else 
                {
                    int tmp=0;
                    SegmentTree2::split(Rt[p],tmp,0,lim,x);
                    Rt[p-1]=SegmentTree2::merge(Rt[p-1],tmp);
                    SegmentTree1::update(RT1,-lim,lim,p-1,x);
                    SegmentTree1::update(RT1,-lim,lim,p,-x);
                    break;
                }
                if(x==0)break;
                
            }
        
        }
    }
}