#include <bits/stdc++.h>
#include <bits/extc++.h>

using namespace std;
using namespace __gnu_pbds;

#define SZ(x) ((int)((x).size()))
#define lb(x) ((x) & (-(x)))
#define bp(x) __builtin_popcount(x)
#define bpll(x) __builtin_popcountll(x)
#define mkp make_pair
#define pb push_back
#define fi first
#define se second
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;
typedef pair<double, int> pdi;
typedef __gnu_pbds::tree<pli, null_type, greater<pli>, __gnu_pbds::rb_tree_tag, 
        __gnu_pbds::tree_order_statistics_node_update> rbt;

void solve() {
    int n, m; ll k;
    cin >> n >> m >> k;
    vector a(n + 1, 0ll);
    const ll D = 1e18;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        a[i] += D;
    }
    sort(a.begin() + 1, a.begin() + n + 1);

    map<ll, int> rid;
    map<int, ll> pt;
    map<int, int> pos;
    int mxid = 0, secid = 0;
    for (int i = 1; i <= n; i++) {
        ll p = a[i] / k;
        if (!rid[p]) {
            rid[p] = ++mxid;
            pt[mxid] = p;
            pos[mxid] = i - 1;
        }
    }
    secid = mxid - 1;
    int t = 0;

    vector tr(n + 1, rbt());
    for (int i = 1; i <= n; i++) {
        ll p = a[i] / k, q = a[i] % k;
        tr[rid[p]].insert({q, ++t});
    }
    int mxdc = 0;

    auto merge = [&](int x, int y) -> int {
        if (tr[x].size() > tr[y].size()) {
            swap(x, y);
        }
        for (auto cur : tr[x]) {
            tr[y].insert(cur);
        }
        tr[x].clear();
        return y;
    };

    while (m--) {
        char op;
        cin >> op;
        if (op == 'C') {
            ll t;
            cin >> t;
            while (true) {
                int tot = tr[mxid].size();
                if (mxdc + t < tot) {
                    mxdc += t;
                    break;
                } else if (secid == 0) {
                    t -= (tot - mxdc);
                    pt[mxid] = pt[mxid] - 1 - (t / tot);
                    mxdc = t % tot;
                    break;
                } else {
                    t -= (tot - mxdc);
                    mxdc = 0;
                    if ((pt[mxid] - 1 - pt[secid]) * tot > t) { 
                        pt[mxid] = pt[mxid] - 1 - (t / tot);
                        mxdc = t % tot;
                        break;
                    } else {
                        t -= (pt[mxid] - 1 - pt[secid]) * tot;
                        mxid = merge(mxid, secid);
                        pt[mxid] = pt[secid];
                        secid--;
                    }
                }
            }
        } else {
            int x;
            cin >> x;
            int tot = tr[mxid].size();
            if (x <= tot - mxdc) {
                cout << tr[mxid].find_by_order(mxdc + x)->fi + k * pt[mxid] - D << '\n';
            } else {
                int sectot = tr[secid].size();
                if (x <= tot + sectot) {
                    x -= tot - mxdc;
                    ll l = 0, r = 2e18, ans = -1;
                    while (l <= r) {
                        ll mid = (l + r) >> 1;
                        int gecnt = tr[secid].order_of_key({mid - pt[secid] * k, 0}) +
                                min((int)tr[mxid].order_of_key({mid + k - pt[mxid] * k, 0}), mxdc);
                        if (gecnt >= x) {
                            ans = mid;
                            l = mid + 1;
                        } else {
                            r = mid - 1;
                        }
                    }
                    cout << ans - D << '\n';
                } else {
                    x -= (tot + sectot);
                    cout << a[pos[secid] - x + 1] - D << '\n';
                }
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int T = 1;
    while (T--) solve();
    return 0;
}