// 
#include <cstdio>
#include <algorithm>

#include <utility>

#define mid ((L + R) >> 1)
#define ls (u << 1)
#define rs (u << 1 | 1)
#define lson ls, L, mid
#define rson rs, mid + 1, R

const long long INF = 1e18;

const int N = 5e5;

int n, m;
int id[N + 5];
int order[N + 5];

long long k, x;
long long a[N + 5];
long long r[N + 5];

char opt[3];

struct sgt {
	int mn[N * 4 + 5];
	int sum[N * 4 + 5];
	
	void pushup(int u) {
		mn[u] = std::min(mn[ls], mn[rs]);
		sum[u] = sum[ls] + sum[rs];
	}
	
	void build(int u = 1, int L = 1, int R = n) {
		if (L == R) { mn[u] = n; sum[u] = 0; return ; }
		build(lson); build(rson); pushup(u);
	}
	
	void upd(int x, int y, int u = 1, int L = 1, int R = n) {
		if (L == R) return sum[u] += y, mn[u] = L, void();
		x <= mid ? upd(x, y, lson) : upd(x, y, rson); pushup(u);
	}
	
	int asksum(int ql, int qr, int u = 1, int L = 1, int R = n) {
		if (qr < L || ql > R) return 0;
		if (ql <= L && R <= qr) return sum[u];
		return asksum(ql, qr, lson) + asksum(ql, qr, rson);
	}
	
	std::pair<int, int> askpos(int ql, int qr, int siz, int u = 1, int L = 1, int R = n) {
		if (qr < L || ql > R || !siz || !sum[u]) return { -1, siz };
		if (ql <= L && R <= qr && sum[u] <= siz) return { mn[u], siz - sum[u] };
		auto now = askpos(ql, qr, siz, rson);
		if (now.second) now = askpos(ql, qr, now.second, lson);
		return now;
	}
} T;

int pos, pre;

long long mx;

void add() {
	while (pos <= n && a[pos] / k == mx) {
		T.upd(id[pos++], 1);
	}
}

void add2() {
	while (pos <= n && a[pos] / k == mx - 1 && id[pos] > pre) {
		T.upd(id[pos++], 1);
	}
}

void decrease(long long x) {
	if (!x) {
		return ;
	}
	int presum = T.asksum(1, pre);
	if (x < presum) {
		auto now = T.askpos(1, pre, x);
		pre = now.first - 1;
		add2();
	} else {
		mx -= 1;
		add();
		x -= presum;
		pre = n;
		if (x) {
			int sum = pos - 1;
			long long t = x / sum;
			if (pos > n || mx - t > a[pos] / k) {
				mx -= t;
				x -= t * sum;
				decrease(x);
			} else {
				long long t = mx - a[pos] / k;
				mx -= t;
				x -= t * sum;
				add();
				decrease(x);
			}
		}
	}
}

int main() {
	#ifdef LOCAL
		freopen("data.in", "r", stdin);
//		freopen("data.out", "w", stdout);
	#endif
	scanf("%d %d %lld", &n, &m, &k);
	for (int i = 1; i <= n; i++)
		scanf("%lld", &a[i]);
	std::sort(a + 1, a + n + 1, std::greater<>());
	for (int i = 1; i <= n; i++)
		order[i] = i;
	std::sort(order + 1, order + n + 1, [&](int x, int y) {
		return a[x] % k < a[y] % k;
	});
	for (int i = 1; i <= n; i++) {
		id[order[i]] = i;
		r[i] = a[order[i]] % k;
	}
	T.build(); pos = 1; pre = n; mx = a[1] / k; add();
	while (m--) {
		scanf("%s %lld", opt, &x);
		if (opt[0] == 'C') {
			decrease(x);
		} else {
			if (x < pos) {
				int sum = T.asksum(1, pre);
				if (x <= sum) {
					auto now = T.askpos(1, pre, x);
					auto ans = k * mx + r[now.first];
					printf("%lld\n", ans);
				} else {
					x -= sum;
					auto now = T.askpos(1, n, x);
					auto ans = k * (mx - 1) + r[now.first];
					printf("%lld\n", ans);
				}
			} else {
				printf("%lld\n", a[x]);
			}
		}
	}
	return 0;
}

answer.code: In function ‘int main()’:
answer.code:117:42: error: ‘greater’ is not a member of ‘std’
  117 |         std::sort(a + 1, a + n + 1, std::greater<>());
      |                                          ^~~~~~~
answer.code:117:50: error: expected primary-expression before ‘>’ token
  117 |         std::sort(a + 1, a + n + 1, std::greater<>());
      |                                                  ^
answer.code:117:52: error: expected primary-expression before ‘)’ token
  117 |         std::sort(a + 1, a + n + 1, std::greater<>());
      |                                                    ^
answer.code:114:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  114 |         scanf("%d %d %lld", &n, &m, &k);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
answer.code:116:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  116 |                 scanf("%lld", &a[i]);
      |                 ~~~~~^~~~~~~~~~~~~~~
answer.code:129:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  129 |                 scanf("%s %lld", opt, &x);
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~~