#include <bits/stdc++.h>

using namespace std;

#define SZ(x) ((int)((x).size()))
#define lb(x) ((x) & (-(x)))
#define bp(x) __builtin_popcount(x)
#define bpll(x) __builtin_popcountll(x)
#define mkp make_pair
#define pb push_back
#define fi first
#define se second
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;
typedef pair<double, int> pdi;

mt19937 mrnd(std::chrono::steady_clock::now().time_since_epoch().count());
int rnd(int l, int r) {
    return mrnd() % (r - l + 1) + l;
}
double rnd01() {
    return mrnd() * 1.0 / UINT32_MAX;
}

namespace Fhq_Treap {
    const int MAXN = 5e5 + 10;

    struct Node {
        int lson, rson;
        int pri, sz;
        ll val;    
    };
    
    int cnt_id;
    Node tree[MAXN << 4];
    queue<int> rub;
    #define ls(x) tree[x].lson
    #define rs(x) tree[x].rson
    
    struct Tree {
        int rt = 0;
        void clear(int x) {
            tree[x].val = tree[x].pri = tree[x].sz = 0;
            rub.push(x);
        }
        void all_clear() {
            auto vec = iter_id();
            for (auto x : vec) {
                clear(x);
            }
        }
        vector<int> iter_id() {        // 中序遍历
            vector<int> res;
            auto dfs = [&](auto &&self, int x) -> void {
                if (ls(x)) {
                    self(self, ls(x));
                }
                res.push_back(x);
                if (rs(x)) {
                    self(self, rs(x));
                }
            };
            dfs(dfs, rt);
            return res;
        }
        vector<ll> iter_val() {
            vector<ll> res;
            auto dfs = [&](auto &&self, int x) -> void {
                if (ls(x)) {
                    self(self, ls(x));
                }
                res.push_back(tree[x].val);
                if (rs(x)) {
                    self(self, rs(x));
                }
            };
            dfs(dfs, rt);
            return res;
        }
        int newp(ll val) {
            int cur;
            if (!rub.empty()) {
                cur = rub.front();
                rub.pop();
            } else {
                cur = ++cnt_id;
            }
            tree[cur].val = val;
            tree[cur].pri = rnd(1, 114514);
            tree[cur].sz = 1;
            return cur;
        }
        void push_up(int x) {
            tree[x].sz = tree[ls(x)].sz + tree[rs(x)].sz + 1;
        }
        void split(int x, int &l, int &r, ll val) {
            if (!x) {
                l = r = 0;
                return ;
            }
            if (tree[x].val <= val) {
                l = x;
                split(rs(x), rs(l), r, val);
            } else {
                r = x;
                split(ls(x), l, ls(r), val);
            }
            push_up(x);
        }
        int merge(int x, int y) {
            if (!x || !y) {
                return x ^ y;
            }
            if (tree[x].pri <= tree[y].pri) {
                rs(x) = merge(rs(x), y);
                return push_up(x), x;
            } else {
                ls(y) = merge(x, ls(y));
                return push_up(y), y;
            }
        }
        void insert(ll val) {
            int l_rt, r_rt;
            split(rt, l_rt, r_rt, val);
            rt = merge(merge(l_rt, newp(val)), r_rt);
        }
        void del(ll val) {
            int l_rt, r_rt, mid_rt;
            split(rt, l_rt, r_rt, val);
            split(l_rt, l_rt, mid_rt, val - 1);
            mid_rt = merge(ls(mid_rt), rs(mid_rt));
            rt = merge(merge(l_rt, mid_rt), r_rt);
        }
        int size() {
            return tree[rt].sz;
        }
        int greater_equal_cnt(ll val) {
            int l_rt, r_rt;
            split(rt, l_rt, r_rt, val - 1);
            int res = tree[r_rt].sz;
            rt = merge(l_rt, r_rt);
            return res;
        }
        ll kth_mx(int k) {
            int x = rt;
            while (true) {
                if (tree[rs(x)].sz + 1 < k) {
                    k -= tree[rs(x)].sz + 1;
                    x = ls(x);
                }
                else if (tree[rs(x)].sz + 1 > k) {
                    x = rs(x);
                }
                else {
                    return tree[x].val;
                }
            }
        }
    };
}
using Fhq_Treap::Tree;

void solve() {
    int n, m; ll k;
    cin >> n >> m >> k;
    vector a(n + 1, 0ll);
    const ll D = 1e18;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        a[i] += D;
    }
    sort(a.begin() + 1, a.begin() + n + 1);

    map<ll, int> rid;
    map<int, ll> pt;
    map<int, int> pos;
    int mxid = 0, secid = 0;
    for (int i = 1; i <= n; i++) {
        ll p = a[i] / k;
        if (!rid[p]) {
            rid[p] = ++mxid;
            pt[mxid] = p;
            pos[mxid] = i - 1;
        }
    }
    secid = mxid - 1;

    vector tr(n + 1, Tree());
    for (int i = 1; i <= n; i++) {
        ll p = a[i] / k, q = a[i] % k;
        tr[rid[p]].insert(q);
    }
    int mxdc = 0;

    auto merge = [&](int x, int y) -> int {
        if (tr[x].size() > tr[y].size()) {
            swap(x, y);
        }
        auto vec = tr[x].iter_val();
        for (auto cur : vec) {
            tr[y].insert(cur);
        }
        tr[x].all_clear();
        return y;
    };

    while (m--) {
        char op;
        cin >> op;
        if (op == 'C') {
            ll t;
            cin >> t;
            while (true) {
                int tot = tr[mxid].size();
                if (mxdc + t < tot) {
                    mxdc += t;
                    break;
                } else if (secid == 0) {
                    t -= (tot - mxdc);
                    pt[mxid] = pt[mxid] - 1 - (t / tot);
                    mxdc = t % tot;
                } else {
                    t -= (tot - mxdc);
                    mxdc = 0;
                    if ((pt[mxid] - 1 - pt[secid]) * tot > t) { 
                        pt[mxid] = pt[mxid] - 1 - (t / tot);
                        mxdc = t % tot;
                        break;
                    } else {
                        t -= (pt[mxid] - 1 - pt[secid]) * tot;
                        pt[mxid] = pt[secid];
                        mxid = merge(mxid, secid);
                        secid--;
                    }
                }
            }
        } else {
            int x;
            cin >> x;
            int tot = tr[mxid].size();
            if (x <= tot - mxdc) {
                cout << tr[mxid].kth_mx(mxdc + x) + k * pt[mxid] - D << '\n';
            } else {
                int sectot = tr[secid].size();
                if (x <= tot + sectot) {
                    x -= tot - mxdc;
                    ll l = 0, r = 2e18, ans = -1;
                    while (l <= r) {
                        ll mid = (l + r) >> 1;
                        int gecnt = tr[secid].greater_equal_cnt(mid - pt[secid] * k) +
                                min(tr[mxid].greater_equal_cnt(mid + k - pt[mxid] * k), mxdc);
                        if (gecnt >= x) {
                            ans = mid;
                            l = mid + 1;
                        } else {
                            r = mid - 1;
                        }
                    }
                    cout << ans - D << '\n';
                } else {
                    x -= (tot + sectot);
                    cout << a[pos[secid] - x + 1] - D << '\n';
                }
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int T = 1;
    while (T--) solve();
    return 0;
}