#include <bits/stdc++.h>
using namespace std;
const int N=5e5+10;
int n,m,k;
long long a[N],b[N],c[N],id[N],t,x,sum,cnt;
__int128 suf[N];
signed tree[N*25],l[N*25],r[N*25],root[N];
bool cmp(int x,int y){
	if(c[x]!=c[y])return c[x]>c[y];
	return x>y;
}
void update(signed &rt,int left,int right,int x){
	++cnt;l[cnt]=l[rt];r[cnt]=r[rt];
	tree[cnt]=tree[rt]+1;rt=cnt; 
	if(left==right)return;
	int mid=(left+right)>>1;
	if(x<=mid)update(l[rt],left,mid,x);
	else update(r[rt],mid+1,right,x);
}
int query(int rt,int left,int right,int L,int R){
	if(left>=L&&right<=R)return tree[rt];
	int mid=(left+right)>>1,res=0;
	if(L<=mid)res+=query(l[rt],left,mid,L,R);
	if(mid<R)res+=query(r[rt],mid+1,right,L,R);
	return res;
}
map <int,int> tid;
int check(__int128 x,int debug){
	auto it=tid.upper_bound((x%k+k)%k);
	int cnt=0;
	int pos=upper_bound(a+1,a+1+n,x)-a;
	if(it!=tid.end()){
		int rid=it->second;
		cnt=query(root[rid],1,n,pos,n);
	}
	//if(debug)cout<<"de "<<cnt<<"\n";
	__int128 all=0;
	if(x>=0)all=suf[pos]-(n-pos+1)*(x/k)+cnt;
	else all=suf[pos]-(n-pos+1)*-((-x-1)/k+1)+cnt;
	__int128 tmp=sum;
	//if(debug)cout<<"de "<<tmp<<"\n";
	tmp-=(all-(n-pos+1));
	tmp=max(tmp,(__int128)0);
	tmp=min(tmp,(__int128)n-pos+1);
	//if(debug)cout<<"de "<<all<<" "<<tmp<<" "<<pos<<" "<<n-(tmp+pos-1)+1<<"\n";
	return n-(tmp+pos-1)+1;
}
signed main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin>>n>>m>>k;
	for(int i=1;i<=n;i++)
		cin>>a[i],id[i]=i;
	sort(a+1,a+1+n);
	for(int i=1;i<=n;i++)
		b[i]=a[i]/k,c[i]=a[i]%k;
	sort(id+1,id+1+n,cmp);
	for(int i=1;i<=n;i++){
		root[id[i]]=root[id[i-1]];
		tid[c[id[i]]]=id[i];
		update(root[id[i]],1,n,id[i]);
	}
	for(int i=n;i>=1;i--)
		suf[i]=suf[i+1]+b[i];
	while(m--){
		string op;
		cin>>op;
		if(op=="C"){
			cin>>t;
			sum+=t;
		}else{
			cin>>x;
			long long l=-1e18,r=1e18;
			while(l<r){
				long long mid=(l+r)>>1;
				if(check(mid,0)<=x){
					r=mid;
				}else{
					l=mid+1;
				}
			}
			cout<<l<<"\n";
		}
	}
	return 0;
}