#include<bits/stdc++.h>
#define all(x) begin(x), end(x)
using namespace std;
using ll = long long;
struct Fenwick {
vector<int> f;
Fenwick(int N) : f(N + 1) {}
void update(int p, int d) {
++p;
for(; p < f.size(); p += p & -p)
f[p] += d;
}
int search(int x) {
int pos = 0, cur = 0;
for(int z = 1<<20; z>>=1;)
if((pos + z) < f.size() && cur + f[pos + z] <= x) {
pos += z;
cur += f[pos];
}
return pos;
}
friend int double_search(const Fenwick &a, const Fenwick &b, int x) {
int pos = 0, cur = 0;
for(int z = 1<<20; z>>=1;)
if((pos + z) < a.f.size() &&
cur + a.f[pos + z] + b.f[pos + z] <= x) {
pos += z;
cur += a.f[pos];
cur += b.f[pos];
}
return pos;
}
};
int main() {
cin.tie(0)->sync_with_stdio(0);
ll n, m, k;
cin >> n >> m >> k;
vector<array<ll, 2>> comp;
vector<ll> a(n);
for(int i = 0; i < n; i++) {
cin >> a[i];
comp.push_back({(a[i] % k + k) % k, i});
}
sort(all(comp));
map<ll, vector<int>, greater<>> blocks;
for(int i = 0; i < n; i++) {
int t = lower_bound(all(comp), array<ll, 2>{(a[i] % k + k) % k, i}) - comp.begin();
ll div = a[i] >= 0 ? a[i] / k : (a[i] - k + 1) / k;
blocks[div].push_back(t);
}
sort(all(a));//for handling prefix
ll block_id = 1ll<<62, count = 0;
Fenwick A(n), B(n);
auto upload_block = [&](int first = 0) {
auto it = blocks.begin();
for(auto i : it->second) {
A.update(i, 1);
if(!first)
B.update(i, -1);
}
count += it->second.size();
block_id = it->first;
blocks.erase(it);
if(!blocks.empty()) {
it = blocks.begin();
for(auto i : it->second)
B.update(i, 1);
}
};
upload_block(1);
ll ops = 0, t;
char c;
while(m--) {
cin >> c >> t;
if(c == 'C') {
ops += t;
while(ops >= count) {
ll cycles_do = ops / count;
ll cycles_max = 1ll<<60;
if(blocks.size())
cycles_max = block_id - blocks.begin()->first;
if(cycles_do >= cycles_max) {
ops -= cycles_max * count;
upload_block();
} else {
ops -= cycles_do * count;
block_id -= cycles_do;
}
}
} else {
t = n - t;
ll bcount = blocks.empty() ? 0 : blocks.begin()->second.size();
ll ccount = n - bcount - count;
ll b_id = blocks.empty() ? -(1ll<<60) : blocks.begin()->first;
if(m == 632)
cout << t << "_" << acount << "_" << bcount << "_" << ccount << "_";
if(t < ccount) {
cout << a[t] << '\n';
} else {
int ahead_idx = count - 1 - ops;
int acount = ahead_idx + 1;
int ans;
ll base;
if(t >= n - acount) {
t -= n - acount;
ans = A.search(t);
base = block_id * k;
} else if(b_id == block_id - 1) {
base = blocks.begin()->first * k;
ans = B.search(t - ccount);
int head = A.search(ahead_idx);
if(ans >= head) {
ans = double_search(A, B, t - ccount + acount);
}
} else {
// int abcount = count - acount;
if(t >= n - count) {
t -= (n - count);
base = (block_id - 1) * k;
ans = A.search(t + acount);
} else {
t -= ccount;
base = b_id;
ans = B.search(t);
}
}
cout << base + comp[ans][0] << '\n';
}
}
}
}