#include <bits/stdc++.h>

#define ios std::ios::sync_with_stdio(0), std::cin.tie(0)
#define endl '\n'

using namespace std;
using i64 = int64_t;

const int N = 5e5 + 5;
i64 n, m, k, a[N], rem[N], len;
map<i64, int> rnk;
i64 d, sz, cnt;

struct SegTree {
#define ls (u << 1)
#define rs (u << 1 | 1)
#define mid ((l + r) >> 1)

    struct Node {
        int l, r, cnt;
    };

    vector<Node> tr;

    SegTree(int n = 0) : tr(n << 2) {}

    void build(int u, int l, int r) {
        tr[u].l = l, tr[u].r = r, tr[u].cnt = 0;
        if (l == r) return;
        build(ls, l, mid), build(rs, mid + 1, r);
    }

    void pushup(int u) { tr[u].cnt = tr[ls].cnt + tr[rs].cnt; }

    void update(int u, int p) {
        int l = tr[u].l, r = tr[u].r;
        if (l == r) {
            tr[u].cnt++;
            return;
        }
        if (p <= mid) update(ls, p);
        else update(rs, p);
        pushup(u);
    }

    i64 query(int u, int k) {
        int l = tr[u].l, r = tr[u].r;
        if (l == r) return rem[l];
        if (k <= tr[ls].cnt) return query(ls, k);
        else return query(rs, k - tr[ls].cnt);
    }

#undef mid
#undef rs
#undef ls
} tr;

void change(i64 t) {
    if (cnt + t < sz) {
        cnt += t;
        i64 r = tr.query(1, cnt);
        while (sz < n && a[sz + 1] / k == d - 1 && a[sz + 1] % k >= r) {
            tr.update(1, rnk[a[++sz] % k]), cnt++;
        }
    } else {
        t -= (sz - cnt), cnt = 0, d--;
        while (sz < n && a[sz + 1] / k >= d - (t / sz)) {
            t -= (d - a[sz + 1] / k) * sz, d = a[sz + 1] / k;
            tr.update(1, rnk[a[++sz] % k]);
        }
        d -= (t / sz), cnt = t % sz;
        if (cnt) {
            i64 r = tr.query(1, cnt);
            while (sz < n && a[sz + 1] / k == d - 1 && a[sz + 1] % k >= r) {
                tr.update(1, rnk[a[++sz] % k]), cnt++;
            }
        }
    }
}

void ask(i64 x) {
    if (x <= sz) {
        if (x <= sz - cnt) {
            i64 r = tr.query(1, x + cnt);
            cout << d * k + r << endl;
        } else {
            i64 r = tr.query(1, x - (sz - cnt));
            cout << (d - 1) * k + r << endl;
        }
    } else cout << a[x] << endl;
}

void solve() {
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++) cin >> a[i], rem[i] = a[i] % k;
    sort(a + 1, a + n + 1, greater<>());

    sort(rem + 1, rem + n + 1, greater<>());
    len = unique(rem + 1, rem + n + 1) - (rem + 1);
    for (int i = 1; i <= n; i++) rnk[rem[i]] = i;
    tr = SegTree(len), tr.build(1, 1, len);

    d = a[1] / k;
    while (sz < n && a[sz + 1] / k == d) tr.update(1, rnk[a[++sz] % k]);

    char op;
    i64 x;
    while (m--) {
        cin >> op >> x;
        if (op == 'C') change(x);
        else ask(x);
    }
}

int main() {
    ios;
    int T = 1;
    while (T--) solve();
    return 0;
}