#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;
i64 d, sz, cnt;
map<i64, int> rnk;

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

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

    int idx;
    vector<Node> tr;

    SegTree(int n = 0) : idx(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 l, int r, int p) {
        if (l == r) {
            tr[u].cnt++;
            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 <= tr[ls].cnt) return query(ls, l, mid, k);
        else return query(rs, mid + 1, r, 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, 1, len, cnt);
        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) break;
            tr.update(1, 1, len, rnk[a[i] % k]), sz++;
        }
        d -= t / sz, cnt = t % sz;
        if (cnt) {
            i64 r = tr.query(1, 1, len, cnt);
            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 (cnt + x <= sz) {
            i64 r = tr.query(1, 1, len, cnt + x);
            cout << d * k + r << endl;
        } else {
            i64 r = tr.query(1, 1, len, 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 <= len; i++) rnk[rem[i]] = i;
    tr = SegTree(len), tr.build(1, 1, 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;
}