/*
Things to notice:
1. do not calculate useless values
2. do not use similar names
 
Things to check:
1. submit the correct file
2. time (it is log^2 or log)
3. memory
4. prove your naive thoughts 
5. long long
6. corner case like n=0,1,inf or n=m
7. check if there is a mistake in the ds or other tools you use
8. fileio in some oi-contest

9. module on time 
10. the number of a same divisor in a math problem
11. multi-information and queries for dp and ds problems
*/
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define pii pair<long long,long long>
#define mp make_pair
#define pb push_back
const int mod=998244353;
const int inf=0x3f3f3f3f;
const int INF=1e18;
int t[500005];
int lowbit(int x)
{
	return x&(-x);	
} 
void update(int x,int d)
{
	for(int i=x;i<=500000;i+=lowbit(i)) t[i]+=d;
}
int query(int x)
{
	int res=0;
	for(int i=x;i>=1;i-=lowbit(i)) res+=t[i];
	return res;
}
int n,m,cb,Q,K;

int a[500005];
pii b[500005];
int getid(pii x)
{
	return lower_bound(b+1,b+1+cb,x)-b;
}
int dv[500005];
vector <pii > rem[500005];
int j=1,ops=0;
int calc(int lim,int d1,int d2)
{
	int tot=0;
	int L=d2+1,R=n,res=d2;
	while(L<=R)
	{
		int mid=(L+R)>>1;
		if(a[mid]>=lim) res=mid,L=mid+1;
		else R=mid-1;
	} 
	tot+=res-d2;
//	cout<<lim<<" "<<tot<<"\n";
	R=cb,L=d1;
	L=max(L,lower_bound(b+1,b+1+cb,mp(lim+(ops/d2+1)*K-dv[j]*K,-1LL))-b);
	if(L<=R) tot+=query(R)-query(L-1);
	L=1,R=d1-1;
	L=max(L,lower_bound(b+1,b+1+cb,mp(lim+(ops/d2)*K-dv[j]*K,-1LL))-b);
//	cout<<"... "<<L<<" "<<lim+(ops/d2)*K-dv[j]*K<<"\n";
	if(L<=R) tot+=query(R)-query(L-1);//,cout<<L<<" "<<R<<"\n";
//	system("pause");
	return tot;
}
void solve()
{
	cin>>n>>Q>>K;
	for(int i=1;i<=n;i++) cin>>a[i],a[i]+=INF;
	sort(a+1,a+1+n),reverse(a+1,a+1+n);
	for(int i=1;i<=n;i++) 
	{
		if(!i||a[i]/K!=a[i-1]/K) m++,dv[m]=a[i]/K;
		rem[m].pb(mp(a[i]%K,i)),b[++cb]=mp(a[i]%K,i);
	}
	sort(b+1,b+1+cb);
	for(int l=0;l<rem[1].size();l++) update(getid(rem[1][l]),1);
	for(int i=1;i<=Q;i++) 
	{
		char op;
		cin>>op;
		if(op=='C') 
		{
			int c;
			cin>>c;
			ops+=c;
			while(j<m&&ops>=(dv[j]-dv[j+1])*query(cb)) 
			{
				ops-=(dv[j]-dv[j+1])*query(cb),j++;
				for(int l=0;l<rem[j].size();l++) update(getid(rem[j][l]),1);
			}
		}
		else
		{
			int c;
			cin>>c;
			int d2=query(cb);
			int req=ops%d2;
			int L=1,R=cb+1,d1=cb+1;
			while(L<=R)
			{
				int mid=(L+R)>>1;
				if(d2-query(mid-1)>=req) d1=mid,L=mid+1;
				else R=mid-1;
			}
//			cout<<d1<<" "<<d2<<" "<<cb<<"\n";
			L=0,R=2e18;
			int res=0;
			
			while(L<=R)
			{
				int mid=(L+R)>>1;
				if(calc(mid,d1,d2)>=c) res=mid,L=mid+1;
				else R=mid-1;
			}
			cout<<res-INF<<"\n";
		}
	}
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	int _=1;
//	cin>>_;
	while(_--) solve();
	return 0;
}

answer.code: In function ‘long long int calc(long long int, long long int, long long int)’:
answer.code:70:14: error: no matching function for call to ‘max(long long int&, long int)’
   70 |         L=max(L,lower_bound(b+1,b+1+cb,mp(lim+(ops/d2+1)*K-dv[j]*K,-1LL))-b);
      |           ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/11/bits/char_traits.h:39,
                 from /usr/include/c++/11/ios:40,
                 from /usr/include/c++/11/istream:38,
                 from /usr/include/c++/11/sstream:38,
                 from /usr/include/c++/11/complex:45,
                 from /usr/include/c++/11/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:54,
                 from answer.code:20:
/usr/include/c++/11/bits/stl_algobase.h:254:5: note: candidate: ‘template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)’
  254 |     max(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/11/bits/stl_algobase.h:254:5: note:   template argument deduction/substitution failed:
answer.code:70:14: note:   deduced conflicting types for parameter ‘const _Tp’ (‘long long int’ and ‘long int’)
   70 |         L=max(L,lower_bound(b+1,b+1+cb,mp(lim+(ops/d2+1)*K-dv[j]*K,-1LL))-b);
      |           ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/11/bits/char_traits.h:39,
                 from /usr/include/c++/11/ios:40,
                 from /usr/include/c++/11/istream:38,
                 from /usr/include/c++/11/sstream:38,
                 from /usr/include/c++/11/complex:45,
                 from /usr/include/c++/11/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:54,
                 from answer.code:20:
/usr/include/c++/11/bits/stl_algobase.h:300:5: note: candidate: ‘template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)’
  300 |     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/11/bits/stl_algobase.h:300:5: note:   template argument deduction/substitution failed:
answer.code:70:14: note:   deduced conflicting types for parameter ‘const _Tp’ (‘long long int’ and ‘long int’)
   70 |         L=max(L,lower_bound(b+1,b+1+cb,mp(lim+(ops/d2+1)*K-dv[j]*K,-1LL))-b);
      |           ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/11/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:65,
                 from answer.code:20:
/usr/include/c++/11/bits/stl_algo.h:3461:5: note: candidate: ‘template<class _Tp> constexpr _Tp std::max(std::initializer_list<_Tp>)’
 3461 |     max(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/11/bits/stl_algo.h:3461:5: note:   template argument deduction/substitution failed:
answer.code:70:14: note:   mismatched types ‘std::initializer_list<_Tp>’ and ‘long long int’
   70 |         L=max(L,lower_bound(b+1,b+1+cb,mp(lim+(ops/d2+1)*K-dv[j]*K,-1LL))-b);
      |           ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/11/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:65,
                 from answer.code:20:
/usr/include/c++/11/bits/stl_algo.h:3467:5: note: candidate: ‘template<class _Tp, class _Compare> constexpr _Tp std::max(std::initializer_list<_Tp>, _Compare)’
 3467 |     max(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/11/bits/stl_algo.h:3467:5: note:   template argument deduction/substitution failed:
answer.code:70:14: note:   mismatched types ‘std::initializer_list<_Tp>’ and ‘long long int’
   70 |         L=max(L,lower_bound(b+1,b+1+cb,mp(lim+(ops/d2+1)*K-dv[j]*K,-1LL))-b);
      |           ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
answer.code:73:14: error: no matching function for call to ‘max(long long int&, long int)’
   73 |         L=max(L,lower_bound(b+1,b+1+cb,mp(lim+(ops/d2)*K-dv[j]*K,-1LL))-b);
      |           ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/11/bits/char_traits.h:39,
                 from /usr/include/c++/11/ios:40,
                 from /usr/include/c++/11/istream:38,
                 from /usr/include/c++/11/sstream:38,
                 from /usr/include/c++/11/complex:45,
                 from /usr/include/c++/11/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:54,
                 from answer.code:20:
/usr/include/c++/11/bits/stl_algobase.h:254:5: note: candidate: ‘template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)’
  254 |     max(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/11/bits/stl_algobase.h:254:5: note:   template argument deduction/substitution failed:
answer.code:7...