#include<bits/stdc++.h>
#include<bits/extc++.h>

using namespace std;
using namespace __gnu_pbds;

typedef long long llint;
typedef pair <llint, llint> pi;

template <class T>
using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

const int MAXN = 500005;

llint n, m, k;
llint a[MAXN];

llint idx, ost, ofs;
map <llint, llint> mp_top_k, mp_ostali;
Tree <pi> top_k;
Tree <pi> ostali;

llint get_mod_k (llint val) {
    val %= k;
    if (val < 0) return val + k;
    return val;
}

llint get_val (llint j) {
    llint res = ofs * k + (top_k.find_by_order(j) -> first);
    if (j < idx) res += k;
    return res;
}

void update_ostali () {
    if (ostali.empty()) {
        ost = -1;
        return;
    }
    llint siz = top_k.size();
    llint val = ostali.begin() -> first;
    llint ostatak = get_mod_k(val);
    auto it = top_k.upper_bound({ostatak, 1e18});
    if (it != top_k.begin()) {
        it--;
    } else {
        it = top_k.end(); it--;
    }

    llint j = top_k.order_of_key(*it);
    llint val_j = get_val(j);

    ost = (j - idx);
    if (ost < 0) ost += siz;
    ost += ((val - val_j) / k - 1) * siz + 1;
}

void ubaci_top_k (llint val) {
    top_k.insert({val, mp_top_k[val]});
    mp_top_k[val]++;
}

void ubaci_ostali (llint val) {
    ostali.insert({val, mp_ostali[val]});
    mp_ostali[val]++;
}

void init () {
    llint mn = 2e18;
    for (int i = 1; i <= n; i++) {
        mn = min(mn, a[i]);
    }
    for (int i = 1; i <= n; i++) {
        if (a[i] <= mn + k) {
            ubaci_top_k(get_mod_k(a[i]));
        } else {
            ubaci_ostali(a[i]);
        }
    }
    idx = top_k.order_of_key({mn, 0});
    ofs = (mn - get_mod_k(mn)) / k;
    update_ostali();
    cout << "ost je " << ost << endl;
}

void prebaci () {
    pi curr = *top_k.find_by_order(idx);

    llint br = ostali.begin() -> first;
    ostali.erase(ostali.begin());
    ubaci_top_k(get_mod_k(br));

    idx = top_k.order_of_key(curr);
}

void advance_once (llint d) {
    llint siz = top_k.size();

    ofs += d / siz;
    d %= siz;

    llint novi_idx = (idx + d) % siz;
    if (novi_idx < idx) ofs++;
    idx = novi_idx;
}

void advance (llint d) {
    while (ost <= d && ost != -1) {
        advance_once(ost);
        d -= ost;
        prebaci();
        update_ostali();
    }
    if (d > 0) {
        advance_once(d);
        if (ost != -1) ost -= d;
    }
}

llint upit (llint val) {
    llint siz = top_k.size();
    if (val > siz) {
        val -= siz;
        val--;
        return ostali.find_by_order(val) -> first;
    } else {
        val--;
        llint j = (idx + val) % siz;
        return get_val(j);
    }
}

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        a[i] = -a[i];
    }
    init();
    for (int i = 1; i <= m; i++) {
        char tip; llint val;
        cin >> tip >> val;
        if (tip == 'C') {
            advance(val);
        } else {
            cout << -upit(val) << '\n';
        }
    }
    return 0;
}