#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 bit {
    int a[N];
    void add(int x) {for(x=col-x+1;x<=col;x+=x&-x) a[x]++;}
    int ask(int k) {
        int x=0;
        for(int i=1<<__lg(col);i;i>>=1) if(x+i<=col&&a[x+i]<=k) k-=a[x+=i];
        return col-x+1;
    }
} 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.add(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.add(j),sz++;
            }
            if(i>1&&ctm-tim[i]>(mpr[i]-mpr[i-1]-1)*sz) {
                if(!re) {
                    re=sz;
                    x=ctm-tim[i]-(mpr[i]-mpr[i-1]-1)*sz;
                }
                re-=x;
                int y=tr.ask(sz-re);
                while(vc[i-1].size()&&vc[i-1].back()>=y) {
                    sz++; tr.add(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.ask((ctm-tim[i])%sz+x)];
                else ans=(mpr[i]-(ctm-tim[i]+sz-1)/sz)*k+mpc[tr.ask(((ctm-tim[i])%sz+x-1)%sz+1)];
            }
            else {
                if(x<=re) ans=(mpr[i-1]+1)*k+mpc[tr.ask(sz-re+x)];
                else ans=(mpr[i-1])*k+mpc[tr.ask(x-re)];
            }
            printf("%lld\n",ans);
        }
    }
    return 0;
}