#include<bits/stdc++.h>
using namespace std;

#define int long long

const int N=5e5+1e3+7;

struct T{
    signed ls,rs,c;
}t[N*41];

int tot;

vector<int> A;

void update(int x)
{
    t[x].c=t[t[x].ls].c+t[t[x].rs].c;
}

void ins(signed &x,int l,int r,int p)
{
    if(!x)
        x=++tot;
    t[x].c++;
    if(l==r)
        return;
    int mid=(l+r)>>1;
    if(p<=mid)
        ins(t[x].ls,l,mid,p);
    else
        ins(t[x].rs,mid+1,r,p);
}

int merge(int x,int y)
{
    if(!x||!y)
        return x+y;
    if(!t[x].ls&&!t[x].rs)
    { 
        t[x].c+=t[y].c;
        return x;
    }
    t[x].ls=merge(t[x].ls,t[y].ls);
    t[x].rs=merge(t[x].rs,t[y].rs);
    update(x);
    return x;
}

int split(int x,int k)
{
    if(!t[x].ls&&!t[x].rs)
    {
        int y=++tot;
        t[x].c-=k;
        t[y].c=k;
        return y;
    }
    int y=++tot;
    if(k>t[t[x].rs].c)
    {
        t[y].rs=t[x].rs;
        t[x].rs=0;
        t[y].ls=split(t[x].ls,k-t[t[x].rs].c);
    }
    else
    {
        t[y].ls=0;
        t[y].rs=split(t[x].rs,k);
    }
    update(x);
    update(y);
    return y;
}

int qry(int x,int l,int r,int k)
{
    if(l==r)
        return l;
    int mid=(l+r)>>1;
    if(k>t[t[x].rs].c)
        return qry(t[x].ls,l,mid,k-t[t[x].rs].c);
    else
        return qry(t[x].rs,mid+1,r,k);
}

int n,k,a[N],q;

map<int,signed> rt;

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>q>>k;
    for(int i=1;i<=n;i++)
        cin>>a[i],a[i]+=(int)1e18;
    sort(a+1,a+n+1);
    for(int i=1;i<=n;i++)
        A.push_back(a[i]%k);
    sort(A.begin(),A.end());
    for(int i=1;i<=n;i++)
        ins(rt[a[i]/k],0,n-1,lower_bound(A.begin(),A.end(),a[i]%k)-A.begin());
    while(q--)
    {
        string op;
        cin>>op;
        if(op[0]=='C')
        {
            int e;
            cin>>e;
            //merge
            while(1)
            {
                auto R=prev(rt.end());
                if(rt.size()==1)
                    break;
                auto L=prev(R);
                if((R->first-L->first)>e/t[R->second].c)
                    break;
                e-=(R->first-L->first)*t[R->second].c;
                L->second=merge(L->second,R->second);
                rt.erase(R);
            }
            auto R=prev(rt.end());
            int d=e/t[R->second].c;
            auto [X,Y]=*R;
            rt.erase(R);
            e-=d*t[R->second].c;
            rt[X-d]=Y;
            if(e)
            {
                int nt=split(R->second,e);
                rt[R->first-1]=merge(rt[R->first-1],nt);
                if(!t[R->second].c)
                    rt.erase(R);
            }
        }
        else
        {
            int x;
            cin>>x;
            int ox=x;
            auto R=prev(rt.end());
            for(int i=0;i<2;i++)
            {
                if(x>t[R->second].c)
                    x-=t[R->second].c,R--;
                else
                {
                    cout<<A[qry(R->second,0,n-1,x)]+R->first*k-(int)1e18<<"\n";
                    x=0;
                    break;
                }
            }
            if(x)
                cout<<a[n-ox+1]-(int)1e18<<"\n";
        }
    }
}