#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<unordered_map>
#include<algorithm>
using namespace std;
const int N=500005;
int n,m,k;
long long a[N];
long long v[N],tot;
struct Segment_Tree
{
    struct Node
    {
        int ls,rs;
        int cnt;
    }tree[N*70];
    int tot;
    int rt[N];
    Segment_Tree():tot(0)
    {
        memset(rt,0,sizeof(rt));
    }
    int new_node()
    {
        int now=++tot;
        tree[now].ls=tree[now].rs=0;
        tree[now].cnt=0;
        return now;
    }
    void push_up(int i)
    {
        tree[i].cnt=tree[tree[i].ls].cnt+tree[tree[i].rs].cnt;
        return;
    }
    void modify(int &i,long long l,long long r,long long u,long long v)
    {
        if(!i) i=new_node(); 
        if(l==r)
        {
            tree[i].cnt+=v;
            return;
        }
        long long mid=(l+r)/2;
        if(u<=mid) modify(tree[i].ls,l,mid,u,v);
        else modify(tree[i].rs,mid+1,r,u,v);
        push_up(i);
        return;
    }
    int merge(int u,int v,long long l,long long r)
    {
        if(!u) return v;
        if(!v) return u;
        if(l==r)
        {
            tree[u].cnt+=tree[v].cnt;
            return u;
        }
        long long mid=(l+r)/2;
        tree[u].ls=merge(tree[u].ls,tree[v].ls,l,mid);
        tree[u].rs=merge(tree[u].rs,tree[v].rs,mid+1,r);
        push_up(u);
        return u;
    }
    void split(int i,long long l,long long r,int k,int &x,int &y)
    {
        if(!i)
        {
            x=y=0;
            return;
        }
        if(l==r)
        {
            x=i;
            y=new_node();
            tree[x].cnt=k,tree[y].cnt=tree[i].cnt-k;
            return; 
        }
        long long mid=(l+r)/2;
        if(k<=tree[tree[i].ls].cnt)
        {
            y=i;
            split(tree[i].ls,l,mid,k,x,tree[y].ls);
        }
        else
        {
            x=i;
            split(tree[i].rs,mid+1,r,k-tree[tree[i].ls].cnt,tree[x].rs,y);
        }
        push_up(i);
        return;
    }
    long long findkth(int i,long long l,long long r,int k)
    {
        if(!i) return 0;
        if(l==r) return l;
        long long mid=(l+r)/2;
        if(k<=tree[tree[i].ls].cnt) return findkth(tree[i].ls,l,mid,k);
        else return findkth(tree[i].rs,mid+1,r,k-tree[tree[i].ls].cnt);
    }
    long long findkth(int u,int v,long long l,long long r,int k)
    {
        if(l==r) return l;
        long long mid=(l+r)/2;
        if(k<=tree[tree[u].ls].cnt+tree[tree[v].ls].cnt) return findkth(tree[u].ls,tree[v].ls,l,mid,k);
        else return findkth(tree[u].rs,tree[v].rs,mid+1,r,k-tree[tree[u].ls].cnt-tree[tree[v].ls].cnt);
    }
}T;
int siz[N],sum[N];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr),cout.tie(nullptr);
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    sort(a+1,a+n+1);
    for(int i=1;i<=n;i++)
        v[++tot]=a[i]/k;
    sort(v+1,v+tot+1);
    tot=unique(v+1,v+tot+1)-v-1;
    for(int i=1;i<=n;i++)
    {
        int p=lower_bound(v+1,v+tot+1,a[i]/k)-v;
        T.modify(T.rt[p],0,k-1,a[i]%k,1);
        siz[p]++;
    }
    for(int i=1;i<=tot;i++)
        sum[i]=sum[i-1]+siz[i];
    int now=0;
    while(m--)
    {
        char ch;
        long long t;
        cin>>ch>>t;
        if(ch=='C')
        {
            while(t>0)
            {
                if(t<siz[tot]-now) now+=t,t=0;
                else if(now>0)
                {
                    t-=siz[tot]-now;
                    now=0;
                    v[tot]--;
                    if(tot-1>=1&&v[tot]==v[tot-1])
                    {
//                    cerr<<"merge"<<v[tot]<<"\n";
                        T.rt[tot-1]=T.merge(T.rt[tot-1],T.rt[tot],0,k-1);
                        siz[tot-1]+=siz[tot];
                        tot--;
                        sum[tot]=sum[tot-1]+siz[tot];
                    }
                }
                if(t==0) break;
                long long del=t/siz[tot];
                if(tot-1>=1) del=min(del,v[tot]-v[tot-1]);
                v[tot]-=del;
                t-=del*siz[tot];
                if(tot-1>=1&&v[tot]==v[tot-1])
                {
//                    cerr<<"merge"<<v[tot]<<"\n";
                    T.rt[tot-1]=T.merge(T.rt[tot-1],T.rt[tot],0,k-1);
                    siz[tot-1]+=siz[tot];
                    tot--;
                    sum[tot]=sum[tot-1]+siz[tot];
                }
            }
        }
        else if(ch=='A')
        {
//            cerr<<"siz"<<siz[tot]<<" "<<now<<"\n";
            if(t<=siz[tot]-now)
            {
                long long val=T.findkth(T.rt[tot],0,k-1,siz[tot]-now-t+1);
//                cerr<<"val"<<val<<"\n";
                cout<<v[tot]*k+val<<"\n";
                continue;
            }
            else t-=siz[tot]-now;
//            cerr<<"now"<<t<<"\n";
            if(tot-1>=1&&v[tot]==v[tot-1]+1)
            {
//                cerr<<"tonext\n";
                if(t<=siz[tot-1]+now)
                {
                    int nrt;
//                    cerr<<"sss"<<tot<<" "<<T.tree[T.rt[tot]].cnt<<"\n";
                    T.split(T.rt[tot],0,k-1,siz[tot]-now,T.rt[tot],nrt);
//                    cerr<<"split"<<siz[tot]-now<<"\n";
//                    cerr<<"sss"<<T.tree[T.rt[tot]].cnt<<"\n";
//                    cerr<<"sss"<<T.tree[nrt].cnt<<"\n";
//                    cerr<<"kkk"<<siz[tot-1]+now-t+1<<"\n";
                    long long val=T.findkth(T.rt[tot-1],nrt,0,k-1,siz[tot-1]+now-t+1);
                    cout<<v[tot-1]*k+val<<"\n";
                    T.rt[tot]=T.merge(T.rt[tot],nrt,0,k-1);
                    continue;
                }
                else t-=siz[tot-1]+now;
                int l=1,r=tot-2,pos=-1;
                while(l<=r)
                {
                    int mid=(l+r)/2;
                    if(sum[tot-2]-sum[mid-1]>=t) pos=mid,l=mid+1;
                    else r=mid-1;
                }
                long long val=T.findkth(T.rt[pos],0,k-1,siz[pos]-(t-sum[tot-2]-sum[pos])+1);
                cout<<v[pos]*k+val<<"\n";
            }
            else
            {
                if(t<=now)
                {
                    long long val=T.findkth(T.rt[tot],0,k-1,siz[tot]-t+1);
                    cout<<(v[tot]-1)*k+val<<"\n";
                    continue;
                }
                else t-=now;
                int l=1,r=tot-1,pos=-1;
                while(l<=r)
                {
                    int mid=(l+r)/2;
                    if(sum[tot-1]-sum[mid-1]>=t) pos=mid,l=mid+1;
                    else r=mid-1;
                }
                long long val=T.findkth(T.rt[pos],0,k-1,siz[pos]-(t-sum[tot-1]-sum[pos])+1);
                cout<<v[pos]*k+val<<"\n";
            }
//            
        }
    }
    return 0;
}

/*
3 3 5
7 3 9
A 3
C 1
A 2
*/