#include<bits/stdc++.h>
using namespace std;
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_cxx;
using namespace __gnu_pbds;
typedef long long ll;
tree<pair<ll,int>,null_type,less<pair<ll,int>>,rb_tree_tag,tree_order_statistics_node_update> rb;
auto kth(int x)
{
	return *rb.find_by_order(x-1);
}
auto rnk(ll x)
{
	return rb.order_of_key(make_pair(x,0))+1;
}
int main()
{
	ios_base::sync_with_stdio(false);
	int n,m;
	long long k;
	cin>>n>>m>>k;
	vector<ll> a(n+5);
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	sort(a.begin()+1,a.begin()+n+1);
	rb.insert(make_pair(a[n]%k,n));
	ll nowq=a[n]/k;
	int now=n-1;
	int sub=0;
	for(int i=1;i<=m;i++)
	{
		char ty;
		long long t;
		cin>>ty>>t;
		if(ty=='C')
		{
//			cerr<<"change* "<<t<<endl;
			while(t)
			{
				ll nxq=a[now]/k;
				if(now==0)nxq=-1e18;
//				cerr<<"nxq "<<nxq<<", nowq "<<nowq<<' '<<rnk(a[now]%k)<<' '<<n-now-sub+1<<endl;
				if(nxq==nowq-1 and rnk(a[now]%k)==n-now-sub+1)
				{
					rb.insert(make_pair(a[now]%k,now));
					now--;
					sub++;
					continue;
				}
				if(nowq!=nxq)
				{
					int lim=n-now-sub;
					if(t<lim)
					{
						sub+=t,t=0;
//						cerr<<"sub "<<sub<<endl;
					}
					else
					{
						t-=lim,sub=0,nowq--;
//						cerr<<"new nowq "<<nowq<<endl;
					}
					continue;
				}
//				cerr<<"phase 1 t="<<t<<endl;
				ll fulllim=min(nowq-nxq,t/(n-now));
//				cerr<<"all-= "<<fulllim<<endl;
				t-=fulllim*(n-now);
				nowq-=fulllim;
//				cerr<<"phase 2 t="<<t<<endl;
				if(fulllim)continue;
				int lim=n-now-sub-rnk(a[now]%k)+1;
//				cerr<<"lim2 "<<lim<<endl;
				if(lim<=t)
				{
					sub+=lim;t-=lim;
//					cerr<<"new sub "<<sub<<endl;
//					cerr<<"insert "<<a[now]%k<<endl;
					rb.insert(make_pair(a[now]%k,now));
//					sub++;
					now--;
				}
				else
				{
					sub+=t;t=0;
//					cerr<<"new sub "<<sub<<endl;
				}
				if(sub==n-now)
				{
//					cerr<<"clear sub"<<endl;
					sub=0,nowq--;
				}
//				cerr<<"phase 3 t="<<t<<endl;
			}
		}
		else
		{
			t=n+1-t;
//			cerr<<kth(1).first<<' '<<kth(2).first<<' '<<kth(3).first<<endl;
//			cerr<<nowq<<' '<<sub<<endl;
			if(t<=now)cout<<a[t]<<"\n";
			else
			{
				t-=now;
				if(t<=sub)
				{
					cout<<kth(t+(n-now-sub)).first+(nowq-1)*k<<"\n";
				}
				else
				{
					t-=sub;
					cout<<kth(t).first+nowq*k<<"\n";
				}
			}
		}
	}
	
	return 0;
}