#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
#include <bits/stdc++.h>

using namespace __gnu_pbds;
using namespace std;
typedef int uci;
#define int long long
#define F first
#define S second
#define ar array



typedef tree<
pair<int,int>,
null_type,
greater<pair<int,int>>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;


int N, M, K;


int ct = 0;
int bnm = 0;
ordered_set nm;

int ma_after(int x);

void DBGNM() {
    /*cout << "BEGINDBG\n";
    cout << ct << " " << bnm << endl;
    for(auto x: nm) cout << x.first << " "; cout << endl;
    cout << ma_after(0) << endl;
    cout << "ENDBG\n";*/
}

int getmod(int q) {
    int out;
    if(q + ct < nm.size()) {
        out = bnm + (*nm.find_by_order(q + ct)).first;
    } else {
        out = bnm + (*nm.find_by_order(q + ct - nm.size())).first - K;
    }
    return out;
}

int ma_after(int t) {
    int ua = t/nm.size();
    int sh = t % nm.size();
    return getmod(sh) - K*ua;
}

void do_update(int t) {
    int ua = t/nm.size();
    int sh = t % nm.size();
    bnm -= K*ua;
    ct += sh;
    if(ct > nm.size()) {ct -= nm.size(); bnm -= K;}
}

vector<int> A;

void solve(){
    cin >> N >> M >> K;
    A = vector<int>(N);
    for(int i = 0; i < N; i++) {
        cin >> A[i];
    }


    sort(A.begin(), A.end());

    // init nm
    {
        int ma = A.back();

        bnm = (A.back()/K)*K;
        nm.insert({A.back() % K, A.size()-1}); A.pop_back();

        while(A.size() && ma - A.back() < K) {
            if(A.back() % K > ma % K) {
                ct++;
            }
            nm.insert({A.back() % K, A.size()-1}); A.pop_back();
        }

    }

    DBGNM();




    for(int qq = 0; qq < M; qq++) {
        char c; cin >> c;
        int q; cin >> q;
        if(c == 'A') {
            q--;
            if(q >= nm.size()) {
                cout << A[A.size() - 1 - (q - nm.size())] << endl;
            } else {
                cout << getmod(q) << endl;
            }
        } else {
            while(A.size() && ma_after(q) - A.back() < K) {
                int lo = 1;
                int hi = q;
                while(lo < hi) {
                    int mid = (lo+hi)/2;
                    if(ma_after(mid) - A.back() < K) hi = mid;
                    else lo = mid+1;
                }

                //cout << "hi" << hi << endl;

                do_update(hi);
                q -= hi;

                int ma = ma_after(0);

                while(A.size() && ma - A.back() < K) {
                    if(A.back() % K > ma % K) {
                        ct++;
                    }
                    nm.insert({A.back() % K, A.size()-1}); A.pop_back();
                }
            }

            if(q > 0) do_update(q);

            DBGNM();
        }
    }

}

uci main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    solve();
}