//
#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
*/