#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define fi first
#define se second
#define inf 0x3f3f3f3f
using namespace std;
const int N=5e5+5;
int n,m,tot;
ll K,a[N],tag;
int cnt;
pair<ll,int>q[N];
string str;
mt19937 gen(114514);
struct node{
    int l,r,fix,sz;
    ll val;
}t[N];
int newnode(ll val){
    tot++;t[tot].fix=gen(),t[tot].sz=1,t[tot].val=val;
    return tot;
}
void pushup(int p){
    t[p].sz=t[t[p].l].sz+t[t[p].r].sz+1;
}
int build(int l,int r){
    if(l>r)return 0;
    int mid=l+r>>1,p=newnode(a[mid]);
    t[p].r=build(l,mid-1),t[p].l=build(mid+1,r);
    pushup(p);return p;
}
int merge(int x,int y){
    if(!x||!y)return x+y;
    if(t[x].fix>t[y].fix){
        t[x].r=merge(t[x].r,y);
        pushup(x);return x;
    }
    else{
        t[y].l=merge(x,t[y].l);
        pushup(y);return y;
    }
}
void split(int rt,int &x,int &y,int val){
    if(!rt){
        x=y=0;
        return;
    }if(t[t[rt].l].sz+1<=val){
        x=rt;
        split(t[x].r,t[x].r,y,val-t[t[x].l].sz-1);
        pushup(x);
    }
    else{
        y=rt;
        split(t[y].l,x,t[y].l,val);
        pushup(y);
    }
}
void split1(int rt,int &x,int &y,ll val){
    if(!rt){
        x=y=0;
        return;
    }
    if(t[rt].val<=val){
        x=rt;
        split1(t[x].r,t[x].r,y,val);
        pushup(x);
    }
    else{
        y=rt;
        split1(t[y].l,x,t[y].l,val);
        pushup(y);
    }
}
int query(int rt,ll val){
    if(!rt)return 0;
    if(val>=t[rt].val)return t[t[rt].l].sz+1+query(t[rt].r,val);
    return query(t[rt].l,val);
}
int qmax(int rt){
    while(t[rt].r)rt=t[rt].r;
    return t[rt].val;
}
int main(){
    //freopen("data.in","r",stdin);
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n>>m>>K;for(int i=1;i<=n;i++)cin>>a[i];
    sort(a+1,a+1+n),reverse(a+1,a+1+n);
    ll cur=0;
    for(int i=1;i<=m;i++){
        cin>>str;ll x;cin>>x;
        if(str[0]=='A')q[++cnt]={cur,n-x+1};
        else cur+=x;
    }
    int it=1,it1=1;while(it+1<=n&&a[1]-a[it+1]<=K)it++;
    cur=0;int rt1=build(1,it),rt2=build(it+1,n);
    while(it1<=cnt){
        ll tmp=(it==n)?inf:(a[it]-a[it+1]+K-1)/K*it;
        while(it1<=cnt&&q[it1].fi<=cur+tmp){
            ll rest=q[it1].fi-cur,val1=rest/it,val2=rest%it;
            int x,y;split(rt1,x,y,val2);
            ll l=-1e18,r=1e18,res=0;
            while(l<=r){
                ll mid=l+r>>1;
                if(query(x,mid+(tag+val1+1)*K)+query(y,mid+(tag+val1)*K)+query(rt2,mid)>=q[it1].se)res=mid,r=mid-1;
                else l=mid+1;
            }cout<<res<<"\n";
            it1++;rt1=merge(x,y);
        }
        cur+=tmp,tag+=(a[it]-a[it+1]+K-1)/K;
        ll val=qmax(rt1)-tag*K;
        while(it+1<=n&&a[it+1]>=val-K){
            it++;int x,y,z;split(rt2,x,rt2,1);
            split1(rt1,y,z,a[it]+tag*K);
            rt1=merge(merge(y,x),z);
        }
    }
}