#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)

    vector<int> cnt;

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

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

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

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

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

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

void ask(i64 x) {
    if (x <= sz) {
        if (x <= sz - cnt) {
            i64 r = tr.query(1, 1, len, sz - cnt - x);
            cout << d * k + r << endl;
        } else {
            i64 r = tr.query(1, 1, len, x);
            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);
    len = unique(rem + 1, rem + n + 1) - (rem + 1);
    for (int i = 1; i <= len; i++) rnk[rem[i]] = i;
    tr = SegTree(len);

    d = a[1] / k;
    for (int i = 1; i <= n; i++) {
        if (a[i] / k != d) break;
        tr.update(1, 1, len, rnk[a[i] % k]), sz++;
    }

    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;
}