#include<bits/stdc++.h>

using namespace std;

mt19937 rnd(239);

using ll = long long;
using ld = long double;


// начало дд

struct node
{
    node *l, *r;

    ll val;
    ll cnt;
    ll pr;

    node(ll v)
    {
        val = v;
        l = r = nullptr;
        cnt = 1;
        pr = rnd();
    }
};

typedef node * qnode;

ll get_cnt(qnode a)
{
    if(a == nullptr)
    {
        return 0;
    }
    return a->cnt;
}

void update(qnode a)
{
    if(a == nullptr)
    {
        return;
    }

    a->cnt = 1 + get_cnt(a->l) + get_cnt(a->r);
}

void merge(qnode l, qnode r, qnode &a)
{
    if(l == nullptr)
    {
        a = r;
        return;
    }
    if(r == nullptr)
    {
        a = l;
        return;
    }

    if(l->pr > r->pr)
    {
        merge(l->r, r, l->r);
        update(l);
        a = l;
    } else {
        merge(l, r->l, r->l);
        update(r);
        a = r;
    }
}

void split_cnt(qnode &l, qnode &r, qnode a, ll k)
{
    if(a == nullptr)
    {
        l = r = nullptr;
        return;
    }

    if(get_cnt(a->l) >= k)
    {
        split_cnt(l, a->l, a->l, k);
        update(a);
        r = a;
    } else {
        k -= get_cnt(a->l) + 1;
        split_cnt(a->r, r, a->r, k);
        update(a);
        l = a;
    }
}

void split_val(qnode &l, qnode &r, qnode a, ll x)
{
    if(a == nullptr)
    {
        l = r = nullptr;
        return;
    }

    if(a->val >= x)
    {
        split_val(l, a->l, a->l, x);
        update(a);
        r = a;
    } else {
        split_val(a->r, r, a->r, x);
        update(a);
        l = a;
    }
}

// конец дд

ll get(ll k, qnode &root) // K-ый максимум в множестве
{
    ll ans ;
    qnode l, m, r;
    split_cnt(l, m, root, get_cnt(root) - k);
    split_cnt(m, r, m, 1);
    ans = m->val;
    merge(l, m, root);
    merge(root, r, root);

    return ans;
}

struct Grib 
{
    qnode root;

    Grib()
    {
        root = nullptr;
    }

    void insert(ll val)
    {
        qnode l, r;
        split_val(l, r, root, val);
        merge(l, new node(val), root);
        merge(root, r, root);
    }

    
};

void down(Grib &st, ll &lvl, ll &pod, ll k) // сделать K операций
{
    if(pod >= k)
    {
        pod -= k;
        return;
    }

    k -= pod;
    pod = 0;

    ll sz = get_cnt(st.root);

    lvl -= k / sz;
    k = k % sz;

    if(k != 0)
    {
        lvl -= 1;
        pod = sz - k;
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    ll n, m, k;

    cin >> n >> m >> k;

    vector<ll> a(n);
    for(ll i = 0; i < n; ++i)
    {
        cin >> a[i];
        a[i] += 1000000000000000000;
    }

    sort(a.begin(), a.end());
    reverse(a.begin(), a.end());

    Grib st;

    ll lvl = 2000000000000000020;
    ll pod = 0;

    ll nxt = 0;

    for(ll i = 0; i < m; ++i)
    {
        char chr;
        cin >> chr;
        if(chr == 'A')
        {
            while(nxt < a.size() && a[nxt] / k == lvl)
            {
                ll sz = get_cnt(st.root);
                ll mx = get(sz - pod + 1, st.root);
                if(a[nxt] % k <= mx)
                {
                    break;
                }
                st.insert(a[nxt] % k);
                ++nxt;
            }
            ll x;
            cin >> x;

            ll sz = get_cnt(st.root);

            ll ans = 0;

            if(x <= sz)
            {
                if(x <= pod)
                {
                    qnode l, r;
                    qnode root = st.root;

                    split_cnt(l, r, root, pod);
                    ans = get(x, root) + (lvl + 1) * k;

                    merge(l, r, root);

                    st.root = root;
                } else {
                    x -= pod;
                    ans = get(x, st.root) + lvl * k;
                }
            } else {
                x -= 1;
                ans = a[x];
            }
            cout << ans - 1000000000000000000 << '\n';

        } else {
            ll t = 0;
            cin >> t;
            while(nxt < a.size())
            {
                ll i_lvl = a[nxt] / k;
                ll sz = get_cnt(st.root);
                ll mx = pod + (lvl - i_lvl) * sz;
                if(mx >= t)
                {
                    break;
                }
                t -= mx;
                // down(st, lvl, pod, mx);
                lvl = i_lvl;
                pod = 0;
                st.insert(a[nxt] % k);
                ++nxt;
            }

            down(st, lvl, pod, t);
        }
    }
}