#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, m, k;
    cin >> n >> m >> k;

    vector<LL> a(n), b(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        b[i] = a[i] % k;
    }    
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    b.erase(unique(b.begin(), b.end()), b.end());

    int mm = b.size();
    vector<int> info(4 << (__lg(m)));

    #define ls p << 1
    #define rs p << 1 | 1
    auto add = [&](auto &&self, int p, int l, int r, int x, int y) -> void {
        if (l == r) {
            info[p] += y;
            return;
        }
        int mid = (l + r) >> 1;
        if (x <= mid) {
            self(self, ls, l, mid, x, y);
        } else {
            self(self, rs, mid + 1, r, x, y);
        }
        info[p] = info[ls] + info[rs];
    };

    auto query = [&](auto &&self, int p, int l, int r, int x) -> int {
        if (x > info[p]) {
            return -1;
        }
        if (l == r) {
            return l;
        }
        int mid = (l + r) >> 1;
        if (info[ls] >= x) {
            return self(self, ls, l, mid, x);
        } else {
            return self(self, rs, mid + 1, r, x - info[ls]);
        }
    };
    
    auto query1 = [&](int x) {
        return query(query, 1, 0, mm - 1, x);
    };

    auto add1 = [&](LL x) {
        LL t = x % k;
        add(add, 1, 0, mm - 1, lower_bound(b.begin(), b.end(), t) - b.begin(), 1);
    };

    LL cur = a.back() / k;
    int tot = 0;
    int del = 0;

    auto norm = [&]() {
        while (a.size()) {
            if (a.back() / k >= cur) {
                add1(a.back());
                tot++;
                a.pop_back();
            } else if (del > 0 && a.back() / k == cur - 1 && a.back() % k >= b[query1(tot - del + 1)]) {
                add1(a.back());
                tot++;
                del++;
                a.pop_back();
            } else {
                break;
            }
        }
    };
    norm();

    while (m--) {
        char ch;
        LL t;
        cin >> ch >> t;
        if (ch == 'A') {
            t = n - t + 1;
            if (t <= a.size()) {
                cout << a[t - 1] << '\n';
            } else if (t <= a.size() + del) {
                cout << (cur - 1) * k + b[query1(t - a.size() + tot - del)] << '\n';
            } else {
                cout << cur * k + b[query1(t - a.size() - del)] << '\n';
            }
        } else {
            if (t < tot - del) {
                del += t;
            } else {
                t -= tot - del;
                del = 0;
                cur--;

                norm();

                while (t > 0 && a.size()) {
                    if (__int128(cur - a.back() / k) * tot <= t) {
                        t -= (cur - a.back() / k) * tot;
                        cur = a.back() / k;
                        norm();
                    } else {
                        break;
                    }
                }

                cur -= t / tot;
                del = t % tot;
            }
            norm();
        }
    }
    return 0;
}

/*
3 5 5
7 3 9
A 3
C 1
A 2
C 2
A 3
*/