#include<bits/stdc++.h>
typedef long long ll;
typedef __int128 LL;
using namespace std;
const int N=500005;
int n,m,row,col,b[N],c[N];
ll a[N],k,mpr[N],mpc[N];
LL tim[N],ctm;
vector<int> vc[N];
struct sgt {
    int sum[4*N];
    void modify(int x,int p=1,int l=1,int r=col) {
        if(l==r) {sum[p]++; return ;}
        int mid=l+r>>1;
        if(x<=mid) modify(x,p<<1,l,mid);
        else modify(x,p<<1|1,mid+1,r);
        sum[p]=sum[p<<1]+sum[p<<1|1];
    }
    int binary(int v,int p=1,int l=1,int r=col) {
        if(l==r) return l;
        int mid=l+r>>1;
        if(sum[p<<1|1]<v) return binary(v-sum[p<<1|1],p<<1,l,mid);
        return binary(v,p<<1|1,mid+1,r);
    }
} tr;
ll read() {
	ll x=0; char c=getchar();
	for(;c<'0'||c>'9';c=getchar()) if(c=='C'||c=='A') return c=='C';
	for(;c>='0'&&c<='9';c=getchar()) x=x*10+c-48;
	return x;
}
int main() {
    n=read(); m=read(); k=read();
    for(int i=1;i<=n;i++) a[i]=read();
    sort(a+1,a+n+1,[](ll x,ll y){return x>y;});
    for(int i=1;i<=n;i++) mpr[i]=a[i]/k;
    sort(mpr+1,mpr+n+1); row=unique(mpr+1,mpr+n+1)-mpr-1;
    for(int i=1;i<=n;i++) b[i]=lower_bound(mpr+1,mpr+row+1,a[i]/k)-mpr;
    for(int i=1;i<=n;i++) mpc[i]=a[i]%k;
    sort(mpc+1,mpc+n+1); col=unique(mpc+1,mpc+n+1)-mpc-1;
    for(int i=1;i<=n;i++) c[i]=lower_bound(mpc+1,mpc+col+1,a[i]%k)-mpc;
    for(int i=1;i<=n;i++) vc[b[i]].push_back(c[i]);
    for(int i=row,j=0;i>=1;j+=vc[i].size(),i--) {
        sort(vc[i].begin(),vc[i].end());
        tim[i]=tim[i+1]+(LL)j*(mpr[i+1]-mpr[i]);
    }
    for(int i:vc[row]) tr.modify(i);
    for(int i=row,sz=vc[row].size(),re=0;m--;) {
        if(read()) {
            ll x=read();
            ctm+=x;
            for(;i>1&&ctm>=tim[i-1];i--) {
                re=0;
                for(int j:vc[i-1]) tr.modify(j),sz++;
            }
            if(i>1&&ctm-tim[i]>(tim[i-1]-tim[i]-1)*sz) {
                if(!re) {
                    re=sz;
                    x=ctm-tim[i]-(tim[i-1]-tim[i]-1)*sz;
                }
                re-=x;
                int y=tr.binary(sz-re);
                while(vc[i-1].size()&&vc[i-1].back()>=y) {
                    sz++; tr.modify(vc[i-1].back());
                    vc[i-1].pop_back();
                }
            }
        }
        else {
            int x=read();
            if(x>sz) {printf("%lld\n",a[x]); continue;}
            ll ans;
            if(!re) {
                if(x<=sz-(ctm-tim[i])%sz) ans=(mpr[i]-(ctm-tim[i])/sz)*k+mpc[tr.binary((ctm-tim[i])%sz+x)];
                else ans=(mpr[i]-(ctm-tim[i]+sz-1)/sz)*k+mpc[tr.binary(((ctm-tim[i])%sz+x-1)%sz+1)];
            }
            else {
                if(x<=re) ans=(mpr[i-1]+1)*k+mpc[tr.binary(sz-re+x)];
                else ans=(mpr[i-1])*k+mpc[tr.binary(x-re)];
            }
            printf("%lld\n",ans);
        }
    }
    return 0;
}