#include<bits/stdc++.h>
using namespace std;
#define MAXN 500005
#define ll long long
#define ls (p<<1)
#define rs (p<<1|1)
ll n, m, k, arr[MAXN];

ll a[MAXN<<2], X[MAXN], xcnt;
unordered_map<ll, int> mp;
void push_up(int p){
	a[p] = a[ls] + a[rs];
}
void update(int pos, int l, int r, int p){
	if(l == r) return (void) (a[p]++);
	int mid = (l+r)>>1;
	if(pos <= mid) update(pos, l, mid, ls);
	else update(pos, mid+1, r, rs);
	push_up(p);
}
int query(int l, int r, int p, int k){
	if(l == r) return X[l];
	int mid = (l+r)>>1;
	if(a[ls] < k) return query(mid+1, r, rs, k-a[ls]);
	else return query(l, mid, ls, k);
}

bool cmp(ll x, ll y) {return x > y;}


int main(){
	cin>>n>>m>>k;
	for(int i=1;i<=n;i++) scanf("%lld", &arr[i]), X[i] = arr[i] % k;
	sort(arr+1, arr+1+n, cmp);
	sort(X+1, X+1+n);
	xcnt = unique(X+1, X+1+n) - X - 1;
	for(int i=1;i<=xcnt;i++) mp[X[i]] = i;
	ll siz = 1, cnt = 0, div = arr[1] / k;
	update(mp[arr[1] % k], 1, xcnt, 1);
	while(siz < n && arr[siz+1] / k == div) siz++, update(mp[arr[siz] % k], 1, xcnt, 1);
	char op[5]; ll x;
	for(int i=1;i<=m;i++){
		scanf("%s%lld", op, &x);
		// printf("cnt = %lld, siz = %lld, div = %lld\n", cnt, siz, div);
		if(op[0] == 'C'){
			if(cnt + x < siz) {
				cnt += x; 
				ll tmp = query(1, xcnt, 1, (siz+1) - (cnt));
				while(siz < n && arr[siz+1] / k == div-1 && arr[siz+1] % k >= tmp) 
					siz++, update(mp[arr[siz] % k], 1, xcnt, 1), cnt++;
				continue;
			}
			x -= siz - cnt; cnt = 0; div--;
			while(siz < n && arr[siz+1] / k >= div - x / siz) {
				ll tmp = arr[siz+1] / k;
				x -= (div - tmp) * siz;
				div = tmp;
				siz++;
				update(mp[arr[siz] % k], 1, xcnt, 1);
			}
			div -= x / siz;
			cnt += x % siz;
			if(cnt != 0) {
				ll tmp = query(1, xcnt, 1, (siz+1) - (cnt));
				while(siz < n && arr[siz+1] / k == div-1 && arr[siz+1] % k >= tmp) 
					siz++, update(mp[arr[siz] % k], 1, xcnt, 1), cnt++;
			}
		}else{
			if(x <= siz) {
				if(cnt + x <= siz) printf("%lld\n", query(1, xcnt, 1, siz+1 - (cnt+x)) + div * k);
				else printf("%lld\n", query(1, xcnt, 1, siz+1 - (cnt+x-siz)) + (div-1) * k);
			} else printf("%lld\n", arr[x]);
		}
	}
	return 0;
}