#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
// mt19937 rand_num(chrono::system_clock::now().time_since_epoch().count());
// uniform_int_distribution<long long> dist(0, 1000000000);
// #ifndef ONLINE_JUDGE
// #define rand() 1
// #else
// #define rand() dist(rand_num)
// #endif
int n, m, pos, l, r, nxt[500005], len[500005], father[500005];
ll k, x, tmp, a[500005], b[500005];
char op;
struct Segment_Tree {
	int idx, root[500005], lc[10000005], rc[10000005];
	ll cnt[10000005];
	#define mid ((l + r) >> 1)
	int new_node(int k = 0) {
		++idx;
		lc[idx] = lc[k], rc[idx] = rc[k], cnt[idx] = cnt[k];
		return idx;
	}
	void push_up(int k) {
		cnt[k] = cnt[lc[k]] + cnt[rc[k]];
	}
	void change(int& k, const ll& pos, ll l = 0, ll r = ::k - 1) {
	 	if(!k) k = new_node();
		++cnt[k];
		if(l == r) return;
		if(pos <= mid) change(lc[k], pos, l, mid);
		else change(rc[k], pos, mid + 1, r);
	}
	ll ask(int k, int rank, ll l = 0, ll r = ::k - 1) {
		if(l == r) return l;
		if(cnt[rc[k]] >= rank) return ask(rc[k], rank, mid + 1, r);
		else return ask(rc[k], rank - cnt[rc[k]], l, mid);
	}
	ll ask(vector<int>& k, int rank, ll l = 0, ll r = ::k - 1) {
		if(l == r) return l;
		int rsz = 0;
		for(const auto& i : k) rsz += cnt[rc[i]];
		if(rsz >= rank) {
			for(auto& i : k) i = rc[i];
			return ask(k, rank, mid + 1, r);
		}
		else {
			for(auto& i : k) i = lc[i];
			return ask(k, rank - rsz, l, mid);
		}
	}
	int merge(int p, int q, ll l = 0, ll r = ::k - 1) {
		if(!p || !q) return p | q;
		if(l == r) {
			cnt[p] += cnt[q];
			return p;
		}
		lc[p] = merge(lc[p], lc[q], l, mid);
		rc[p] = merge(rc[p], rc[q], mid + 1, r);
		push_up(p);
		return p;
	}
	void split(int k, int rank, int& curl, int& curr, ll l = 0, ll r = ::k - 1) {
		if(!k) {
			curl = curr = 0;
			return;
		}
		curl = new_node(k), curr = new_node(k);
		if(l == r) {
			cnt[curr] = rank;
			cnt[curl] -= rank;
			// cerr << l << " --- " << r << '\n';
			// cerr << curl << " ~ " << cnt[curl] << '\n';
			// cerr << curr << " ~ " << cnt[curr] << '\n';
			return;
		}
		if(cnt[rc[k]] >= rank) {
			lc[curr] = 0;
			split(rc[curr], rank, rc[curl], rc[curr], mid + 1, r);
		}
		else {
			rc[curl] = 0;
			split(lc[curl], rank - cnt[rc[k]], lc[curl], lc[curr], l, mid);
		}
		push_up(curl);
		push_up(curr);
	}
	// void dfs(int k, ll l = 0, ll r = k - 1) {
	// 	if(!k) return;
	// 	cerr << ">>> " << k << ": " << l << " " << r << " " << cnt[k] << " " << lc[k] << " " << rc[k] << '\n';
	// 	dfs(lc[k], l, mid);
	// 	dfs(rc[k], mid + 1, r);
	// }
} tree;
int findset(int x) {return father[x] == x ? x : father[x] = findset(father[x]);}
void move_pos(int delta) {
	pos += delta;
	if(pos == len[1]) {
		--b[1];
		pos = 0;
	}
}
void merge() {
	b[1] = b[nxt[1]];
	tree.root[1] = tree.merge(tree.root[1], tree.root[nxt[1]]);
	len[1] += len[nxt[1]];
	father[nxt[1]] = 1;
	nxt[1] = nxt[nxt[1]];
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n >> m >> k;
	for(int i = 1; i <= n; ++i) cin >> a[i];
	stable_sort(a + 1, a + 1 + n, greater<ll>());
	for(int i = 1; i <= n; i = nxt[i]) {
		b[i] = a[i] / k;
		nxt[i] = i + 1;
		while(nxt[i] <= n && a[nxt[i]] / k == b[i]) ++nxt[i];
	}
	b[n + 1] = 1ll << 60;
	for(int i = 1; i <= n; i = nxt[i]) {
		len[i] = nxt[i] - i;
		for(int j = i; j < nxt[i]; ++j) {
			father[j] = i;
			tree.change(tree.root[i], a[j] % k);
		}
	}
	while(m--) {
		cin >> op >> x;
		if(op == 'C') {
			if(pos) {
				// cerr << x << " " << min((ll)len[1] - pos, x) << "?\n";
				tmp = min((ll)len[1] - pos, x);
				move_pos(tmp);
				// cerr << "* " << x << '\n';
				x -= tmp;
				// cerr << "! " << x << '\n';
			}
			if(b[1] == b[nxt[1]]) merge();
			while(x >= len[1] && nxt[1] <= n) {
				if(x >= (b[1] - b[nxt[1]]) * len[1]) {
					x -= len[1] * (b[1] - b[nxt[1]]);
					merge();
				}
			}
			b[1] -= x / len[1];
			x %= len[1];
			move_pos(x);
		}
		else {
			if(!pos || x > len[1] + len[nxt[1]]) cout << (tree.ask(tree.root[findset(x)], x - (findset(x) - 1)) + b[findset(x)] * k) << '\n';
			else {
				tree.split(tree.root[1], pos, l, r);
				// cerr << tree.cnt[l] << " - " << tree.cnt[r] << '\n';
				// tree.dfs(r);
				if(x <= len[1] - pos) cout << (tree.ask(l, x) + b[1] * k) << '\n';
				else {
					cout << (tree.ask(*new vector<int>({r, tree.root[nxt[1]]}), x - tree.cnt[l]) + (b[1] - 1) * k) << '\n';
				}
				tree.root[1] = tree.merge(l, r);
			}
		}
		// cerr << pos << '\n';
		// for(int i = 1; i <= n; i = nxt[i]) {
		// 	cerr << i << ": " << len[i] << " " << nxt[i] << " " << b[i] << '\n';
		// }
		// for(int i = 1; i <= n; ++i) cerr << findset(i) << " \n"[i == n];
	}
	return 0;
}
/*
3 5 5
7 3 9
A 3
C 1
A 2
C 2
A 3
*/