/*
世界の果てさえ
【世界的尽头在何处】
仆らは知らない
【我们也无从知晓】
*/
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <vector>
#include <set>
#include <map>
#define pr pair <int, int>
#define mr make_pair
#define int __int128
#define LL long long
#define ls tree[p].L
#define rs tree[p].R
using namespace std;
const int MAXN = 5e5 + 5;
int n, m, k, a[MAXN], lsh[MAXN], tot, ys[MAXN], now[MAXN], Bit[MAXN];
char F[5];
void read(int &x) {
	x = 0; bool f = 1; char C = getchar();
	for(; C < '0' || C > '9'; C = getchar()) if(C == '-') f = 0;
	for(; C >= '0' && C <= '9'; C = getchar()) x = (x << 1) + (x << 3) + (C ^ 48);
	x = (f ? x : -x);
}
int lowbit(int x) { return x & (-x); }
void update(int x, int val) {
	for(int i = x; i <= tot; i += lowbit(i)) Bit[i] += val;
}
int asksum(int x) {
	int ans = 0;
	for(int i = x; i; i -= lowbit(i)) ans += Bit[i];
	return ans;
}
signed main() {
	read(n); read(m); read(k);
	for(int i = 1; i <= n; i ++) read(a[i]);
	sort(a + 1, a + 1 + n, [&](int x, int y) { return x > y; });
	for(int i = 1; i <= n; i ++) lsh[++ tot] = a[i] % k, ys[i] = a[i] % k;
	sort(lsh + 1, lsh + 1 + tot); tot = unique(lsh + 1, lsh + 1 + tot) - lsh - 1;
	for(int i = 1; i <= n; i ++) ys[i] = lower_bound(lsh + 1, lsh + 1 + tot, ys[i]) - lsh;
	int x, pre = 0;
	for(int i = 1; i <= n; i ++) {
		int t = asksum(ys[i] - 1); 
		now[i] = pre - (i - 1) * (a[i] / k) + (i - 1 - t) + 1;
		pre += a[i] / k; update(ys[i], 1);
	//	printf("|%lld|", (LL)now[i]);
	}
	int nowc = 0;
	for(int i = 1; i <= m; i ++) {
		scanf("%s", F + 1); read(x);
		if(F[1] == 'C') nowc += x;
		else {
			int t = upper_bound(now + 1, now + 1 + n, nowc) - now; t --;
			if(t == 0 && 0) printf("%lld\n", x == 1 ? (LL)(a[1] - nowc * k) : (LL)a[x]);
			else {
		//		printf("?%lld?", (LL)t);
				if(x > t + 1) {
					printf("%lld\n", (LL)a[x]); continue;
				}
				if(t + 1 <= n && a[t] - a[t + 1] < k && nowc + t + 1 >= now[t + 1]) {
					int q = nowc - now[t], val = a[t];
					int nowid = q % t == 0 ? t : q % t, trn = q % t == 0 ? q / t : q / t + 1;
			//		printf("?%lld %lld %lld?", (LL)x, (LL)t, (LL)nowid);
					if(x <= t - nowid) {
						int nowval = a[x + nowid] - (a[x + nowid] - a[t]) / k * k;
						while(nowval >= a[t]) nowval -= k;
						printf("%lld\n", (LL)(nowval - (trn - 1) * k));
					}
					else if(x == t - nowid + 1) {
						printf("%lld\n", (LL)a[t + 1]);
					}
					else if(x <= t + 1) {
						x -= (t - nowid + 1);// printf("$%lld$", (LL)x);
						int nowval = a[x] - (a[x] - a[t]) / k * k;
						while(nowval >= a[t]) nowval -= k;
						printf("%lld\n", (LL)(nowval - trn * k));
					}
					else printf("%lld\n", (LL)a[x]);
				}
				else {
					int q = nowc - now[t], val = a[t];
					int nowid = q % t == 0 ? t : q % t, trn = q % t == 0 ? q / t : q / t + 1;
		//			printf("|%lld %lld %lld|", (LL)t, (LL)nowid, (LL)x);
					if(x <= t - nowid) {
						int nowval = a[x + nowid] - (a[x + nowid] - a[t]) / k * k;
						while(nowval >= a[t]) nowval -= k;
						printf("%lld\n", (LL)(nowval - (trn - 1) * k));
					}
					else if(x <= t) {
						x -= (t - nowid);
						int nowval = a[x] - (a[x] - a[t]) / k * k;
						while(nowval >= a[t]) nowval -= k;
		//				printf("|%lld %lld|", (LL)x, (LL)nowval);
						printf("%lld\n", (LL)(nowval - trn * k));
					}
					else printf("%lld\n", (LL)a[x]);
				}
			}
		}
	}
	return 0;
}
/*
3 5 5
7 3 9
A 3
C 1
A 2
C 2
A 3
*/