//Author: Kevin
#include<bits/stdc++.h>
//#pragma GCC optimize("O2")
using namespace std;
#define ll long long
#define ull unsigned ll
#define pb emplace_back
#define mp make_pair
#define ALL(x) (x).begin(),(x).end()
#define rALL(x) (x).rbegin(),(x).rend()
#define srt(x) sort(ALL(x))
#define rev(x) reverse(ALL(x))
#define rsrt(x) sort(rALL(x))
#define sz(x) (int)(x.size())
#define inf 0x3f3f3f3f
#define pii pair<int,int>
#define lb(v,x) (int)(lower_bound(ALL(v),x)-v.begin())
#define ub(v,x) (int)(upper_bound(ALL(v),x)-v.begin())
#define uni(v) v.resize(unique(ALL(v))-v.begin())
#define longer __int128_t
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
void die(string S){puts(S.c_str());exit(0);}
array<ll,3> A[500500];
tree<pair<ll,int>,null_type,greater<pair<ll,int>>,rb_tree_tag,tree_order_statistics_node_update> tr;
tree<pair<ll,int>,null_type,greater<pair<ll,int>>,rb_tree_tag,tree_order_statistics_node_update> tr2;
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n,m,k;
	cin>>n>>m>>k;
	for(int i=1;i<=n;i++)
	{
		ll x;
		cin>>x;
		A[i]={x/k,x%k,i};
	}
	sort(A+1,A+n+1);
	reverse(A+1,A+n+1);
	int p=1;
	ll sum=0;
	tr.insert(mp(A[1][1],-A[1][2]));
	for(int i=2;i<=n;i++)
		tr2.insert(mp(A[i][0]*k+A[i][1],A[i][2]));
	while(m--)
	{
		char ch;
		cin>>ch;
		if(ch=='C')
		{
			ll x;
			cin>>x;
			sum+=x;
		}
		while(p<n&&(A[p][0]-A[p+1][0])*p<=sum)
		{
			sum-=(A[p][0]-A[p+1][0])*p;
			tr.insert(mp(A[p+1][1],-A[p+1][2]));
			tr2.erase(mp(A[p+1][0]*k+A[p+1][1],A[p+1][2]));
			p++;
		}
		if(ch=='A')
		{
			int x;
			cin>>x;
			int cnt=sum%p;
			if(x>p)
			{
				cout<<tr2.find_by_order(x-p-1)->first<<'\n';
			}
			else if(x<=p-cnt)
			{
				ll val=tr.find_by_order(cnt+x-1)->first;
				cout<<val+(A[p][0]-sum/p)*k<<'\n';
			}
			else
			{
				ll val=tr.find_by_order(x-p+cnt-1)->first;
				cout<<val+(A[p][0]-sum/p-1)*k<<'\n';
			}
		}
	}
	return 0;
}