#include<bits/stdc++.h>
using namespace std;
int n,m,r;
const int N=500005;
#define ll long long
ll k;
ll a[N];
vector<ll> v;
map<ll,int> mp;
int t[N*4],_t[N*4];
ll nowx,nowp,nowy;
char s[100];
ll o;
void add(int x,int l,int r,int y)
{
    ++t[x];
    if (l==r)
        return;
    int mid=(l+r)/2;
    if (y<=mid)
        add(x*2,l,mid,y);
    else
        add(x*2+1,mid+1,r,y);
}
int ask(int x,int l,int r,int y)
{
    if (y==0)
        return r+1;
    if (l==r)
        return l;
    int mid=(l+r)/2;
    if (t[x*2+1]>=y)
        return ask(x*2+1,mid+1,r,y);
    else
        return ask(x*2,l,mid,y-t[x*2+1]);
}
inline void upd()
{
    while (nowp<n&&a[nowp+1]/k>=nowx)
    {
        ++nowp;
        add(1,1,r,mp[a[nowp]%k]);
    }
    // upd2();
}
inline void clear(int x,int l,int r)
{
    if (_t[x]==0||l==r)
        return;
    _t[x]=0;
    int mid=(l+r)/2;
    clear(x*2,l,mid);
    clear(x*2+1,mid+1,r);
}
void add2(int x,int l,int r,int y)
{
    ++_t[x];
    if (l==r)
        return;
    int mid=(l+r)/2;
    if (y<=mid)
        add2(x*2,l,mid,y);
    else
        add2(x*2+1,mid+1,r,y);
}
inline void upd2()
{
    clear(1,1,r);
    for (int i=nowp+1;i<=n;++i)
        if (a[i]/k==nowx-1)
            add2(1,1,r,mp[a[i]%k]);
}
int ask2(int x,int l,int r,int y)
{
    if (l==r)
        return l;
    int mid=(l+r)/2;
    if (t[x*2+1]+_t[x*2+1]>=y)
        return ask2(x*2+1,mid+1,r,y);
    else
        return ask2(x*2,l,mid,y-t[x*2+1]-_t[x*2+1]);
}
int main()
{
    scanf("%d%d%lld",&n,&m,&k);
    for (int i=1;i<=n;++i)
    {
        scanf("%lld",&a[i]);
        v.push_back(a[i]%k);
    }
    sort(v.begin(),v.end());
    v.erase(unique(v.begin(),v.end()),v.end());
    r=v.size();
    for (int i=0;i<(int)v.size();++i)
        mp[v[i]]=i+1;
    sort(a+1,a+1+n,greater<ll>());
    nowx=a[1]/k;
    upd();
    upd2();
    ll o;
    while (m--)
    {
        scanf("%s%lld",s,&o);
        if (s[0]=='C')
        {
            if (nowy+o<t[1])
            {
                nowy+=o;
            }
            else
            {
                nowx--;
                upd2();
                o-=(t[1]-nowy);
                nowy=0;
                ll nnowx=nowx-o/t[1],nnowy=o%t[1];
                while (nowp<n&&nnowx<=a[nowp+1]/k)
                {
                    o-=(nowx-a[nowp+1]/k)*k;
                    nowx=a[nowp+1]/k;
                    upd();
                    upd2();
                    nnowx=nowx-o/t[1],nnowy=o%t[1];
                }
                nowx=nnowx;
                upd2();
                nowy=nnowy;
            }
        }
        else
        {
            if (o>t[1]+_t[1])
                printf("%lld\n",a[o]);
            else
            {
                if (o<=t[1]-nowy)
                {
                    printf("%lld\n",v[ask(1,1,r,nowy+o)-1]+nowx*k);
                }
                else
                {
                    int z=ask(1,1,r,nowy+1);
                    int _z=ask2(1,1,r,o-(t[1]-nowy));
                    // cout<<"?"<<z<<' '<<_z<<endl;
                    if (z<_z)
                    {
                        printf("%lld\n",v[_z-1]+(nowx-1)*k);
                    }
                    else
                        printf("%lld\n",a[o]);
                    // printf("%lld\n",v[ask(1,1,r,o-(t[1]-nowy))-1]+(nowx-1)*k);
                }
            }
        }
    }
    return 0;
}