#include <bits/stdc++.h>
using namespace std;
#define int long long

const int maxn = 1e18;
struct merge_segtree{
    int n , m , cnt = 0; //树上点的个数，总点个数
    vector<int> maxx , sum , lson , rson , root , ans;
    merge_segtree(int N,int M) {
        n = N;
        m = M;
        sum.resize(m << 4);
        lson.resize(m << 4);
        rson.resize(m << 4);
        root.resize(n + 10);
    }

    void pushup(int x) {
        sum[x] = sum[lson[x]] + sum[rson[x]];
    }

    void update(int &k,int l,int r,int x,int v) {
        if(k == 0) k = ++cnt;
        if(l == r) {
            sum[k] += v;
            return ;
        }
        int mid = l + r >> 1;
        if(x <= mid) update(lson[k] , l , mid , x , v);
        if(x > mid) update(rson[k] , mid + 1 , r , x , v);
        pushup(k);
    }

    int merge(int a,int b,int l,int r) {
        if(a == 0 || b == 0) return a + b;
        if(l == r) {
            sum[a] += sum[b];
            return a;
        }
        int mid = l + r >> 1;
        lson[a] = merge(lson[a] , lson[b] , l , mid);
        rson[a] = merge(rson[a] , rson[b] , mid + 1 , r);
        pushup(a);
        return a;
    }

    int get_kth(int x,int k,int l,int r) {
        if(l == r) return l;
        int mid = l + r >> 1;
        if(k > sum[rson[x]]) return get_kth(lson[x] , k - sum[rson[x]] , l , mid);
        return get_kth(rson[x] , k , mid + 1 , r);
    }

    int get_range(int k,int x,int y,int l,int r) {
        if(l >= x && r <= y) return sum[k];
        int mid = l + r >> 1;
        int res = 0;
        if(x <= mid && lson[k]) res += get_range(lson[k] , x , y , l , mid);
        if(y > mid && rson[k]) res += get_range(rson[k] , x , y , mid + 1 , r);
        return res;
    }
};

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0) , cout.tie(0);
    int n , m , k;
    cin >> n >> m >> k;
    vector<int> a(n + 1);
    for(int i = 1;i <= n;i ++) 
        cin >> a[i];
    sort(a.begin() + 1 , a.begin() + 1 + n);
    
    auto group = [](int x,int k) {
        if(x < 0) return x / k - 1;
        return x / k;
    };

    merge_segtree mst(n , n);
    int cnt = 0;
    map<int , int> M;
    map<int , int> ref;
    map<int , int> num;
    for(int i = 1;i <= n;i ++) {
        
        int g = group(a[i] , k);
        if(!M[g]) {
            M[g] = ++cnt;
            ref[cnt] = g;
        }
        int now = M[g];
        num[now] ++;
        int seat;
        if(a[i] > 0) seat = a[i] % k + 1;
            else seat = (a[i] + 1) % k + k;
        mst.update(mst.root[now] , 1 , k , seat , 1);

    }

    vector<int> del(cnt + 2);
    vector<int> gs(cnt + 2);
    for(int i = cnt;i >= 1;i --) {
        gs[i] = gs[i + 1] + num[i];
        del[i] = gs[i] * (ref[i] - ref[i - 1]);
    }

    int sum = 0 , maxc = cnt;
    while(m --) {
        char c;
        int x;
        cin >> c >> x;
        if(c == 'C') {
            sum += x;
            while(cnt > 1 && sum >= del[cnt]) {
                sum -= del[cnt];
                mst.root[maxc] = mst.merge(mst.root[maxc] , mst.root[cnt - 1] , 1 , k);
                cnt --;
            }
            // cout << "fk! " << sum << ' ' << cnt << "\n";
        } else {

            if(cnt == 1) {
                int wz = sum % gs[cnt];
                if(x <= gs[cnt] - wz) {
                    int ans = mst.get_kth(mst.root[maxc] , x + wz , 1 , k);
                    cout << (ref[cnt] - sum / gs[cnt]) * k + ans - 1 << "\n";
                } else {
                    int ans = mst.get_kth(mst.root[maxc] , x - (gs[cnt] - wz) , 1 , k);
                    cout << (ref[cnt] - sum / gs[cnt] - 1) * k + ans - 1 << "\n";
                }
                continue;
            }

            if(cnt > 2 && x > gs[cnt - 1]) {
                int now = n - x + 1;
                cout << a[now] << "\n";
            } else {
                if(sum <= del[cnt] - gs[cnt]) {
                    int wz = sum % gs[cnt];
                    if(x > gs[cnt]) {
                        int now = n - x + 1;
                        cout << a[now] << "\n";
                    } else {
                        if(x <= gs[cnt] - wz) {
                            int ans = mst.get_kth(mst.root[maxc] , x + wz , 1 , k);
                            cout << (ref[cnt] - sum / gs[cnt]) * k + ans - 1 << "\n";
                        } else {
                            int ans = mst.get_kth(mst.root[maxc] , x - (gs[cnt] - wz) , 1 , k);
                            cout << (ref[cnt] - sum / gs[cnt] - 1) * k + ans - 1 << "\n";
                        }
                    }
                } else {
                    int wz = sum % gs[cnt];
                    if(x <= gs[cnt] - wz) {
                        int ans = mst.get_kth(mst.root[maxc] , x + wz , 1 , k);
                        cout << (ref[cnt] - sum / gs[cnt]) * k + ans - 1 << "\n";
                    } else {
                        int l = 1 , r = k;
                        x -= (gs[cnt] - wz);
                        int ans = -1;
                        while(l <= r) {
                            int mid = l + r >> 1;
                            int rg = mst.get_range(mst.root[cnt - 1] , mid , k , 1 , k) + min(mst.get_range(mst.root[maxc] , mid , k , 1 , k) , wz);
                            if(rg >= x) {
                                ans = mid;
                                l = mid + 1;
                            } else r = mid - 1;
                        }
                        cout << (ref[cnt] - sum / gs[cnt] - 1) * k + ans - 1 << "\n";
                    }
                }
            }
        }
    }
    return 0;
}