#include<bits/stdc++.h>
using namespace std;
#define cs const
#define re register
#define fi first
#define se second
#define pb push_back
#define ll long long
cs int RLEN=1<<20|1;
#define gc getchar
inline int read(){
	char ch=gc();
	int res=0;bool f=1;
	while(!isdigit(ch))f^=ch=='-',ch=gc();
	while(isdigit(ch))res=(res+(res<<2)<<1)+(ch^48),ch=gc();
	return f?res:-res;
}
inline ll readll(){
	char ch=gc();
	ll res=0;bool f=1;
	while(!isdigit(ch))f^=ch=='-',ch=gc();
	while(isdigit(ch))res=(res+(res<<2)<<1)+(ch^48),ch=gc();
	return f?res:-res;
}
template<class tp>inline void chemx(tp &a,tp b){a<b?a=b:0;}
template<class tp>inline void chemn(tp &a,tp b){a>b?a=b:0;}

cs int N=500005;
char xxx;
int n,m,k;
ll a[N];
namespace seg{
	cs int M=N*40;
	int lc[M],rc[M];
	int sz[M],tot;
	void insert(int &u,int l,int r,int v){
		if(!u)u=++tot;
		sz[u]++;
		if(l==r){
			return;
		}
		int mid=(l+r)/2;
		if(v<=mid)insert(lc[u],l,mid,v);
		else insert(rc[u],mid+1,r,v);
	}
	int find(int u,int l,int r,int k){
		if(l==r){
			return l;
		}
		int mid=(l+r)/2;
		if(k<=sz[lc[u]])return find(lc[u],l,mid,k);
		else return find(rc[u],mid+1,r,k-sz[lc[u]]);
	}
	void merge(int &r1,int r2,int l,int r){
		if(!r1||!r2){r1=r1+r2;return;}
		sz[r1]+=sz[r2];
		if(l==r)return;
		int mid=(l+r)/2;
		merge(lc[r1],lc[r2],l,mid);
		merge(rc[r1],rc[r2],mid+1,r);
	}
	void split(int &r1,int &r2,int u,int l,int r,int k){
if(u==0)return;
		r1=++tot,r2=++tot;
		int mid=(l+r)/2;
		if(k==0){
			r1=u,r2=0;return;
		}
		if(l==r&&k<sz[u]){
			sz[r2]=k,sz[r1]=sz[u]-k;
			return;
		}
		if(sz[rc[u]]==k){
			lc[r1]=lc[u];
			rc[r1]=0;
			lc[r2]=0;
			rc[r2]=rc[u];
		}
		else if(sz[rc[u]]<k){
			rc[r1]=0;
			rc[r2]=rc[u];
			split(lc[r1],lc[r2],lc[u],l,mid,k-sz[rc[u]]);
		}
		else if(sz[rc[u]]>k){
			lc[r1]=lc[u];
			lc[r2]=0;
			split(rc[r1],rc[r2],rc[u],mid+1,r,k);
		}
		sz[r1]=sz[lc[r1]]+sz[rc[r1]];
		sz[r2]=sz[lc[r2]]+sz[rc[r2]];
	}
}

#define pli pair<ll,int>
char op[5];
char yyy;

int main(){
	#ifdef Stargazer
	freopen("2.in","r",stdin);
	#endif
	//cout<<(&yyy-&xxx)/1024/1024<<'\n';
	n=read(),m=read(),k=read();
	for(int i=1;i<=n;i++)a[i]=readll();
	sort(a+1,a+n+1);
	vector<pli> rt;
	vector<int> sm;
	for(int i=1;i<=n;i++){
		ll v=a[i]/k;
		if(rt.size()&&rt.back().fi==v){
			seg::insert(rt.back().se,0,k-1,a[i]%k);
			sm.back()++;
		}
		else{
			int x=0;
			seg::insert(x,0,k-1,a[i]%k);
			rt.pb(pli(v,x));
			sm.pb(1);
		}
	}
	for(int i=(int)rt.size()-1;i;i--)sm[i-1]+=sm[i];
	for(int tt=1;tt<=m;tt++){
		scanf("%s",op);
		if(op[0]=='C'){
			ll t=readll();
			while(t){
				if(rt.size()==1){
					ll x1=t/n,x2=t%n;
					rt.back().fi-=x1;
					if(x2==0){
						
					}
					else{
						int r1=0,r2=0;
						seg::split(r1,r2,rt.back().se,0,k-1,x2);
						ll x=rt.back().fi;
						rt.pop_back();
						sm.pop_back();
						rt.pb(pli(x-1,r2));
						rt.pb(pli(x,r1));
						sm.pb(n);
						sm.pb(n-x2);
					}
					t=0;
				}
				else{
					int len=rt.size();
					ll del=rt[len-1].fi-rt[len-2].fi;
					if(del*sm.back()<=t){
						t-=del*sm.back();
						seg::merge(rt[len-2].se,rt[len-1].se,0,k-1);
						rt.pop_back();
						sm.pop_back();
					}
					else{
						ll x1=t/sm.back(),x2=t%sm.back();
						rt.back().fi-=x1;
						int r1=0,r2=0;
						seg::split(r1,r2,rt.back().se,0,k-1,x2);
						if(rt[len-2].fi+1==rt[len-1].fi){
							seg::merge(rt[len-2].se,r2,0,k-1);
							rt[len-1].se=r1;
							//sm[len-2]+=x2;
							sm[len-1]=sm[len-1]-x2;
						}
						else{
							ll x=rt.back().fi,y=sm.back();
							rt.pop_back();
							sm.pop_back();	
							rt.pb(pli(x-1,r2));
							rt.pb(pli(x,r1));
							sm.pb(y);
							sm.pb(y-x2);						
						}
						t=0;
					}
				}
			}
		}
		else{
			int x=read();
			int l=0,r=rt.size()-1,res=0;
			while(l<=r){
				int mid=(l+r)/2;
				if(sm[mid]>=x)res=mid,l=mid+1;
				else r=mid-1;
			}
			cout<<rt[res].fi*k+seg::find(rt[res].se,0,k-1,sm[res]-x+1)<<'\n';
		}

	}
}