#include <bits/stdc++.h>

using namespace std;
#define ll long long
#define pii pair<int, int>
#define ld long double
#define all(a) (a).begin(), (a).end()

int cnt[(1 << 20) + 228];

void build(int v, int left, int right) {
    cnt[v] = 0;
    if (left + 1 == right)
        return;
    int mid = (left + right) / 2;
    build(2 * v + 1, left, mid);
    build(2 * v + 2, mid, right);
}

void add(int v, int left, int right, int i, int x) {
    if (left + 1 == right) {
        cnt[v] += x;
        return;
    }
    int mid = (left + right) / 2;
    if (i < mid)
        add(2 * v + 1, left, mid, i, x);
    else
        add(2 * v + 2, mid, right, i, x);
    cnt[v] = cnt[2 * v + 1] + cnt[2 * v + 2];
}

int get_kth(int v, int left, int right, int k) {
    if (left + 1 == right)
        return left;
    int mid = (left + right) / 2;
    if (cnt[2 * v + 1] >= k)
        return get_kth(2 * v + 1, left, mid, k);
    return get_kth(2 * v + 2, mid, right, k - cnt[2 * v + 1]);
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n, m;
    long long k;
    cin >> n >> m >> k;
    vector<long long> A(n);
    for (int i = 0; i < n; ++i)
        cin >> A[i];
    sort(A.begin(), A.end());
    vector<long long> all_rs(n);
    for (int i = 0; i < n; ++i)
        all_rs[i] = A[i] % k;
    sort(all_rs.begin(), all_rs.end());
    all_rs.resize(unique(all_rs.begin(), all_rs.end()) - all_rs.begin());
    int N = all_rs.size();

    build(0, 0, N);

    int cur_sz = 1;
    int cur_l = 0;
    long long cur_m = A.back() / k;
    auto add_num = [&](long long x) {
        x %= k;
        add(0, 0, N, lower_bound(all_rs.begin(), all_rs.end(), x) - all_rs.begin(), 1);   
    };
    add_num(A.back());
    A.pop_back();
    auto fixup_m = [&]() {
        while (!A.empty()) {
            long long m2 = A.back() / k;
            if (m2 == cur_m) {
                // consider cur_l = 0 here
                add_num(A.back());
                A.pop_back();
                ++cur_sz;
            } else if (m2 == cur_m - 1 && cur_l > 0) {
                long long r = A.back() % k;
                if (all_rs[get_kth(0, 0, N, cur_sz - cur_l)] >= r) {
                    add_num(A.back());
                    A.pop_back();
                    ++cur_sz;
                    ++cur_l;
                } else {
                    break;
                }
            } else {
                break;
            }
        }
    };
    fixup_m();
    while (m--) {
        char c;
        long long t;
        cin >> c >> t;
        if (c == 'C') {
            if (t < cur_sz - cur_l) {
                cur_l += t;
            } else {
                t -= cur_sz - cur_l;
                cur_l = 0;
                --cur_m;
                fixup_m();
                while (t >= cur_sz) {
                    long long take = min(t / cur_sz, A.empty() ? t / cur_sz : cur_m - A.back() / k);
                    cur_m -= take;
                    t -= cur_sz * take;
                    fixup_m();
                }
                cur_l = t;
            }
            fixup_m();
        } else {
            t = n + 1 - t;
            if (t <= A.size()) {
                cout << A[t - 1] << '\n';
            } else if (t <= A.size() + cur_l) {
                cout << (cur_m - 1) * k + all_rs[get_kth(0, 0, N, t - A.size() + cur_sz - cur_l)] << '\n';
            } else {
                //cerr << ' ' << t - A.size() - cur_l << '\n';
                //cerr << ' ' << get_kth(0, 0, N, t - A.size() - cur_l) << '\n';
                cout << cur_m * k + all_rs[get_kth(0, 0, N, t - A.size() - cur_l)] << '\n';
            }
        }
    }
    return 0;
}