#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<int,int> mp;
int 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 (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]);
    }
}
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();
    ll o;
    while (m--)
    {
        // cout<<nowx<<' '<<nowy<<' '<<nowp<<' '<<t[1]<<endl;
        scanf("%s%lld",s,&o);
        if (s[0]=='C')
        {
            if (nowy+o<t[1])
            {
                nowy+=o;
            }
            else
            {
                nowx--;
                o-=(t[1]-nowy);
                nowy=0;
                int 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;
                    // cout<<"???"<<nowx<<endl;
                    upd();
                    nnowx=nowx-o/t[1],nnowy=o%t[1];
                }
                nowx=nnowx;
                nowy=nnowy;
            }
        }
        else
        {
            if (o>t[1])
                printf("%lld\n",a[o]);
            else
            {
                if (o<=t[1]-nowy)
                {
                    // cout<<'?'<<v[ask(1,1,r,nowy+o)-1]<<endl;
                    printf("%lld\n",v[ask(1,1,r,nowy+o)-1]+nowx*k);
                }
                else
                {
                    // cout<<'!'<<v[ask(1,1,r,o-(t[1]-nowy))-1]<<endl;
                    printf("%lld\n",v[ask(1,1,r,o-(t[1]-nowy))-1]+(nowx-1)*k);
                }
            }
        }
    }
    return 0;
}