#include <bits/stdc++.h>
#define endl '\n'
#define ll long long
using namespace std;
const int N = 5e5 + 5;
int n, m, k;
int tot;
ll a[N], res[N];
unordered_map<ll, int> mp;
int tree[N << 2];
#define ls (o << 1)
#define rs (o << 1 | 1)
#define Ls ls, l, mid
#define Rs rs, mid + 1, r
inline void modify(const int o, const int l, const int r, const int pos)
{
    if (l == r)
        return tree[pos]++, void();
    const int mid = (l + r) >> 1;
    if (pos <= mid)
        modify(Ls, pos);
    else
        modify(Rs, pos);
    tree[o] = tree[ls] + tree[rs];
}
inline int query(const int o, const int l, const int r, const int k)
{
    if (l == r)
        return res[l];
    const int mid = (l + r) >> 1;
    if (k <= tree[ls])
        return query(Ls, k);
    else
        return query(Rs, k - tree[ls]);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++)
        cin >> a[i], res[i] = a[i] % k;
    sort(a + 1, a + n + 1, [](const ll x, const ll y) { return x > y; });
    sort(res + 1, res + n + 1);
    tot = unique(res + 1, res + n + 1) - res - 1;
    for (int i = 1; i <= tot; i++)
        mp[res[i]] = i;
    int tree_siz = 0, cnt = 0;
    ll Div = a[1] / k;
    // tree_siz 维护段中点数量
    // cnt 被删除的点数量 （显然是从后开始删除的）
    while (tree_siz < n && a[tree_siz + 1] / k == Div)
        modify(1, 1, tot, mp[a[++tree_siz] % k]);
    while (m--)
    {
        static string opt;
        static int x;
        cin >> opt >> x;
        if (opt == "A")
        {
            if (x <= tree_siz)
            {
                if (cnt + x <= tree_siz)
                    cout << (query(1, 1, tot, tree_siz + 1 - (cnt + x)) + Div * k) << endl;
                else
                    cout << (query(1, 1, tot, tree_siz + 1 - (cnt + x - tree_siz)) + (Div - 1) * k) << endl;
            }
            else
                cout << a[x] << endl;
        }
        else
        {
            if (x < tree_siz - cnt)
            {
                cnt += x;
                ll tmp = query(1, 1, tot, tree_siz + 1 - cnt);
                while (tree_siz < n && a[tree_siz + 1] / k == Div - 1 && a[tree_siz + 1] % k >= tmp)
                    modify(1, 1, tot, mp[a[++tree_siz] % k]), cnt++;
                continue;
            }
            x -= tree_siz - cnt;
            cnt = 0;
            Div--;
            while (tree_siz < n && a[tree_siz + 1] / k >= Div - x / tree_siz)
            {
                ll tmp = a[tree_siz + 1] / k;
                x -= (Div - tmp) * tree_siz;
                Div = tmp;
                tree_siz++;
                modify(1, 1, tot, mp[a[tree_siz] % k]);
            }
            Div -= x / tree_siz;
            cnt += x % tree_siz;
            if (cnt != 0)
            {
                ll tmp = query(1, 1, tot, tree_siz + 1 - cnt);
                while (tree_siz < n && a[tree_siz + 1] / k == Div - 1 && a[tree_siz + 1] % k >= tmp)
                    modify(1, 1, tot, mp[a[++tree_siz] % k]), cnt++;
            }
        }
    }
    return 0;
}