#include<bits/stdc++.h>
#define Gc() getchar()
#define Me(x,y) memset(x,y,sizeof(x))
#define Mc(x,y) memcpy(x,y,sizeof(x))
#define d(x,y) ((m)*(x-1)+(y))
#define R(n) (rnd()%(n)+1)
#define Pc(x) putchar(x)
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define eb emplace_back
using namespace std;using ll=long long;using db=double;using lb=long db;using ui=unsigned;using ull=unsigned long long;using pii=pair<int,int>;
const int N=5e5+5,M=N*4+5,K=(1<<25)+5,mod=998244353,Mod=mod-1;const db eps=1e-9;const int INF=1e9+7;mt19937 rnd(time(0));
int n,m;ll k,A[N];
int l[N],r[N],siz[N],rd[N],cnt;ll val[N],g[N];
void Pg(int v,ll w){if(v) val[v]+=w,g[v]+=w;}
void P(int v){if(g[v]) Pg(l[v],g[v]),Pg(r[v],g[v]),g[v]=0;}
void up(int v){siz[v]=siz[l[v]]+siz[r[v]]+1;}
void split1(ll x,int v,int &a,int &b){
	if(!v){a=b=0;return;}P(v);
	if(x>=val[v]) a=v,split1(x,r[v],r[a],b);
	else b=v,split1(x,l[v],a,l[b]);
	up(v);
}
void split2(int x,int v,int &a,int &b){
	if(!v){a=b=0;return;}P(v);
	if(x>=siz[l[v]]+1) a=v,split2(x-siz[l[v]]-1,r[v],r[a],b);
	else b=v,split2(x,l[v],a,l[b]);
	up(v);
}
ll qry(int x,int v){
	P(v);
	if(x==siz[r[v]]+1) return val[v];
	if(x>siz[r[v]]+1) return qry(x-siz[r[v]]-1,l[v]);
	else return qry(x,r[v]);
}
int newn(ll x){siz[++cnt]=1;rd[cnt]=rnd();val[cnt]=x;return cnt;}
int merge(int x,int y){
	if(!x||!y) return x|y;P(x);P(y);
	if(rd[x]<rd[y]) return r[x]=merge(r[x],y),up(x),x;
	else return l[y]=merge(x,l[y]),up(y),y;
}
int qi(int x){while(l[x]) P(x),x=l[x];return val[x];}
int qx(int x){while(r[x]) P(x),x=r[x];return val[x];}
int rt;
using LL=__int128;
void Solve(){
	int i,j;scanf("%d%d%lld",&n,&m,&k);
	for(i=1;i<=n;i++) scanf("%lld",&A[i]);
	sort(A+1,A+n+1);
	int R=n-1;rt=newn(A[n]);
	while(m--){
		char c;c=Gc();while(c<'A'||c>'Z') c=Gc();
		ll x;scanf("%lld",&x);
		if(c=='C'){
			while(R){
				LL w=(LL)(qi(rt)-A[R])/k*(n-R);
				if(w>x) break;
				Pg(rt,-(qi(rt)-A[R])/k*k);x-=w;
				int r1,r2;split1(A[R]+k-1,rt,r1,r2);
				if(siz[r2]<=k){
					Pg(r2,-k);x-=siz[r2];
					rt=merge(merge(newn(A[R]),r2),r1);
					R--;
				}else{rt=merge(r1,r2);break;}
			}
			ll w=x/(n-R);
			Pg(rt,-w*k);x-=w*(n-R);
			int r1,r2;split2((n-R)-x,rt,r1,r2);
			Pg(r2,-k);rt=merge(r2,r1);
		}else{
			printf("%lld\n",x<=n-R?qry(x,rt):A[n-x+1]);
		}
	}
}
int main(){
	int t=1;
	// scanf("%d",&t);
	while(t--) Solve();
	cerr<<clock()*1.0/CLOCKS_PER_SEC<<'\n';
}