// 
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int SZ=1<<20;
char buf[SZ],*p1,*p2;
#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,SZ,stdin),p1==p2)?EOF:*p1++)
ll read(){
	ll n=0; bool m=0;
	char c=gc();
	while(c<'0'||c>'9')m=c=='-',c=gc();
	while(c>='0'&&c<='9')n=(n<<3)+(n<<1)+(c^'0'),c=gc();
	return m?-n:n;
}
mt19937 Rand(time(0));
const int N=5e5+5;
ll a[N];
int rt,lc[N],rc[N],sz[N],key[N],tot;
void pushup(int u){
	sz[u]=sz[lc[u]]+sz[rc[u]]+1;
}
void split(int u,ll x,int &l,int &r){
	if(!u)return l=r=0,void();
	if(a[u]<=x)l=u,split(rc[u],x,rc[u],r);
	else r=u,split(lc[u],x,l,lc[u]);
	pushup(u);
}
int merge(int u,int v){
	if(!u||!v)return u|v;
	if(key[u]<key[v])return rc[u]=merge(rc[u],v),pushup(u),u;
	return lc[v]=merge(u,lc[v]),pushup(v),v;
}
void ins(ll x){
	int u,v;
	split(rt,x,u,v);
	tot++,a[tot]=x,key[tot]=Rand(),pushup(tot);
	rt=merge(merge(u,tot),v);
}
int rk(ll x){
	int u=rt,y=0;
	while(u){
		if(a[u]<=x)u=rc[u];
		else y+=sz[rc[u]]+1,u=lc[u];
	}
	return y;
}
ll getk(int x){
	int u=rt;
	while(1){
		int rsz=sz[rc[u]];
		if(x<=rsz)u=rc[u];
		else if(x<=rsz+1)return a[u];
		else x-=rsz+1,u=lc[u];
	}
}
int n,m,k,c;
ll b[N],pl;
ll modk(ll x){return (x%=k)<0?x+k:x;}
ll getl(ll x){return x-modk(x);}
int main(){
	n=read(),m=read(),k=read();
	for(int i=1;i<=n;i++)b[i]=read();
	stable_sort(b+1,b+n+1),reverse(b+1,b+n+1);
	pl=getl(b[1]);
	for(int i=1;i<=n&&getl(b[i])==pl;i++)ins(modk(b[i]));
	while(m--){
		char op=gc();
		while(op!='A'&&op!='C')op=gc();
		if(op=='A'){
			int x=read();
			if(x<=tot-c)printf("%lld\n",getk(c+x)+pl);
			else if(x<=tot)printf("%lld\n",getk(x-(tot-c))+pl-k);
			else printf("%lld\n",b[x]);
		}else{
			ll x=read();
			while(x){
				if(tot<n&&getl(b[tot+1])==pl-k){
					int y=min(x,(ll)rk(modk(b[tot+1]))-c);
					if(!y)ins(b[tot+1]),c++;
					else c+=y,x-=y;
				}else if(c){
					if(tot-c<=x)x-=tot-c,c=0,pl-=k;
					else c+=x,x=0;
				}else if(x<tot){
					c=x,x=0;
				}else{
					int p=tot<n?getl(b[tot+1])+k:0;
					if(tot<=n&&(pl-p)/k*tot<=x)x-=(pl-p)/k*tot,pl=p;
					else pl-=x/tot*k,x%=tot;
				}
				// printf("%lld %lld %d %d\n",x,pl,c,tot);
			}
		}
	}
	return 0;
}