#pragma GCC optimize(3,"Ofast","inline")
#pragma GCC optimize(2)
#include <bits/stdc++.h>
#define ll long long
#define mod 998244353
#define Ma 500005
#define G 3
#define N 13
#define pb push_back
#define L (1<<21)
#define ls p<<1
#define rs p<<1|1
#define i128 __int128
using namespace std;
ll n,m,k;
ll a[Ma],pn[Ma],need[Ma];
ll pp[Ma];

struct sgtree{
    struct node{
        ll l,r,w;
    }t[Ma];
    void build(ll p,ll l,ll r)
    {
        t[p].l=l,t[p].r=r,t[p].w=0;
        if (l==r)
            return;
        ll mid=(l+r)>>1;
        build(ls,l,mid),build(rs,mid+1,r);
        return;
    }
    void change(ll p,ll l,ll r)
    {
        if (l<=t[p].l&&t[p].r<=r)
        {
            t[p].w++;
            return;
        }
        ll mid=(t[p].l+t[p].r)>>1;
        if (l<=mid) change(ls,l,r);
        if (r>mid) change(rs,l,r);
        t[p].w=t[ls].w+t[rs].w;
        return;
    }
    ll ask(ll p,ll l,ll r)
    {
        if (l>r)
            return 0;
        if (l<=t[p].l&&t[p].r<=r)
            return t[p].w;
        ll val=0;
        ll mid=(t[p].l+t[p].r)>>1;
        if (l<=mid) val+=ask(ls,l,r);
        if (r>mid) val+=ask(rs,l,r);
        return val;
    }
    ll ask2(ll p,ll x)
    {
        if (t[p].l==t[p].r)
            return t[p].l;
        if (x>=t[ls].w)
            return ask2(rs,x-t[ls].w);
        else
            return ask2(ls,x);
        
    }
}T;


void sol()
{
    cin>>n>>m>>k;
    for (ll i=1;i<=n;i++)
        cin>>a[i];
    sort(a+1,a+n+1);
    for (ll i=1;i<=n;i++)
        pn[i]=(a[n]-a[i])/k*k+a[i],pp[i]=pn[i];
    sort(pp+1,pp+n+1);
    ll tot=unique(pp+1,pp+n+1)-(pp+1);
    T.build(1,1,tot);
    i128 ans=0,add=0;
    ll cnt=n-1;
    T.change(1,n,n);
    while (m--)
    {
        char op,t;
        ll x;
        cin>>op>>x;
        if (op=='A')
        {
            if (x>n-cnt)
                printf("%lld\n",a[n-x+1]);
            else
            {
                ll all=n-cnt;
                ll pl=(ans+add)/all,pr=(ans+add)%all+x;
                if (pr>all)
                    pl++,pr-=all;
                ll id=T.ask2(1,all-pr);
                printf("%lld\n",pp[id]-pl*k);
            }
        }
        else
        {
            ans+=x;
            while (cnt)
            {
                ll pw=((a[n]-a[cnt])/k-(a[n]-a[cnt+1])/k)*(n-cnt);
                ll l=lower_bound(pp+1,pp+tot+1,pn[cnt])-pp;
				pw-=T.ask(1,1,l-1);
				pw=max(pw,0ll);
                if (pw>=ans)
                    break;
                ans-=pw,add+=pw;
                add+=(pn[cnt]-a[cnt])/k;
                T.change(1,l,l);
                cnt--;
            }
            //printf("cnt=%lld\n",cnt);
        }
    }
}


int	main(){
    ios::sync_with_stdio(0); cin.tie(0);
    int tt=1;
    //cin>>tt;
    while (tt--)
        sol();
    return 0;
}
/*
3 5 5
7 3 9
A 3
C 1
A 2
C 2
A 3
*/