#include <iostream>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

template<class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>; ///find_by_order(),order_of_key()

#define ll long long
const int N=500050;
ll a[N];

int main(){
	int n,m;
	ll k;
	scanf("%i %i %lld",&n,&m,&k);
	ordered_set<pair<ll,int>> all;
	for(int i=1;i<=n;i++){
		scanf("%lld",&a[i]);
		all.insert({a[i],i});
	}

	ll a=all.rbegin()->first/k;
	ll b=all.rbegin()->first%k;
	if(b<0){
		b+=k;
		a--;
	}
	ll val=a;
	ordered_set<pair<ll,int>> ost;
	ost.insert({b, all.rbegin()->second});
	all.erase(--all.end());
	ll lzy=0;
	while(all.size()){
		ll a=all.rbegin()->first/k;
		ll b=all.rbegin()->first%k;
		if(b<0){
			b+=k;
			a--;
		}
		if(a==val){
			ost.insert({b, all.rbegin()->second});
			all.erase(--all.end());
		}else{
			break;
		}
	}

	while(m--){
		char c;
		ll t;
		scanf("\n%c %lld",&c,&t);
		auto Get=[&](ll t){
			ll ans;
			if(t<=all.size()){
				ans=all.find_by_order(t-1)->first;
			}else{
				t-=all.size();
				ll add=val*k;
				if(t<=lzy){
					t+=(int)ost.size()-lzy;
					add-=k;
				}else{
					t-=lzy;
				}
				ans=ost.find_by_order(t-1)->first+add;
			}
			return ans;
		};
		if(c=='A'){
			t=n-t+1;
			printf("%lld\n",Get(t));
		}else{
			while(t>0){
				if(all.empty()){
					lzy+=t;
					val-=lzy/ost.size();
					lzy%=ost.size();
					break;
				}
				auto pos=*all.rbegin();
				ll mx=pos.first;
				ll a=mx/k;
				ll b=mx%k;
				if(b<0){
					b+=k;
					a--;
				}
				ll need=0;
				auto it=ost.lower_bound({b,0});
				if(it==ost.begin()){
					need=ost.size()*(val-a)-lzy;
				}else{
					need=ost.size()*(val-a)-lzy-ost.order_of_key(*--it)-1;
				}
				ll use=min(need,t);
				lzy+=use;
				t-=use;
				val-=lzy/k;
				lzy%=k;
				if(use==need){
					//printf("[%lld %lld] add %lld\n",val*k, val*k+k-1,mx);
					ost.insert({b,pos.second});
					all.erase(--all.end());
					lzy++;
				}else{
					break;
				}
			}
			//for(int i=1;i<=n;i++){
			//	printf("%lld ",Get(i));
			//}
			//printf("\n");
		}
	}
	return 0;
}