#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 << "_" << count << "_" << 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';
            }
        }
    }
}