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

const int INF = (int)1e9+5;
const int N = 5e5+5;
vector<LL> hsh;
int gethsh(int x){return lower_bound(hsh.begin(), hsh.end(), x)-hsh.begin();}

#define M L+(R-L)/2
#define TN int &o, int L, int R
#define LS nd[o].ch[0], L, M
#define RS nd[o].ch[1], M+1, R

struct Node{
    int ch[2], cnt;
}nd[N*30];
vector<int> bac; int btp=-1, idx=0;
struct Msg{
    LL val; int rtid;
}msg;
map<LL, int, greater<LL>> rt;
Msg blk[N]; int sumblk[N], fr, ed;

int newNode(){
    int id = (btp>=0 ? bac[btp--] : ++idx);
    nd[id].cnt=0; nd[id].ch[0]=nd[id].ch[1]=-INF;
    return id;
}
int delNode(int x){
    ++btp;
    if (btp<bac.size()) bac[btp]=x;
    else bac.push_back(x);
}

int merge(int o, int w){
    if (o<=0) return w;
    if (w<=0) return o;
    nd[o].cnt += nd[w].cnt;
    nd[o].ch[0] = merge(nd[o].ch[0], nd[w].ch[0]);
    nd[o].ch[1] = merge(nd[o].ch[1], nd[w].ch[1]);
    delNode(w);
    return o;
}

void split(int o, int &w, int k){
    if (o<=0 || nd[o].cnt<=k){w=-INF; return;}
    w = newNode();
    int Lval = (nd[o].ch[0]>0 ? nd[nd[o].ch[0]].cnt : 0);
    if (Lval < k) split(nd[o].ch[1], nd[w].ch[1], k-Lval);
    else swap(nd[o].ch[1], nd[w].ch[1]);
    if (Lval > k) split(nd[o].ch[0], nd[w].ch[0], k);
    nd[w].cnt = nd[o].cnt-k;
    nd[o].cnt = k;
}

int find(TN, int val){
//    printf("find(%d %d %d %d) cnt=%d\n", o, L, R, val, (o>0 ? nd[o].cnt : 0));
    if (o<=0 || nd[o].cnt<val) return -1;
    if (L==R) return L;
    int res=find(LS, val);
    if (res>0) return res;
    if (nd[o].ch[0]>0) val -= nd[nd[o].ch[0]].cnt;
    return find(RS, val);
}

void insert(TN, int pos){
    if (o<=0) o=newNode();
    nd[o].cnt++;
    if (L<R){
        if (pos<=M) insert(LS, pos);
        else insert(RS, pos);
    }
}

#undef M
#undef TN
#undef LS
#undef RS

int n, m;
LL k, A[N];

signed main(){
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m >> k;
    for (int i=1; i<=n; ++i){
        cin >> A[i];
        hsh.push_back(A[i]%k);
    }
    hsh.push_back(-1LL);
    sort(hsh.begin(), hsh.end());
    hsh.erase(unique(hsh.begin(), hsh.end()), hsh.end());
//    printf("hsh:"); for (LL x : hsh) printf("%lld ", x); puts("");
    int sz = hsh.size()-1;
    for (int i=1; i<=n; ++i){
        insert(rt[A[i]/k], 1, sz, gethsh(A[i]%k));
    }
    fr=2, ed=1;
    blk[0]=blk[1]=Msg{-INF, -INF}; sumblk[0]=sumblk[1]=0;
    for (auto [val, rtid] : rt){
        ++ed;
        blk[ed] = Msg{val, rtid};
        sumblk[ed] = nd[rtid].cnt+sumblk[ed-1];
    }
//    for (int i=fr; i<=ed; ++i) printf("i=%d val=%lld rtid=%d sumblk=%d\n", i, blk[i].val, blk[i].rtid, sumblk[i]);
    while (m--){
        char opt; LL x; cin >> opt >> x;
        if ('A'==opt){
            int pos = lower_bound(sumblk, sumblk+ed+1, x)-sumblk;
            int fsz = nd[blk[pos].rtid].cnt - (x-sumblk[pos-1]) + 1;
            int fd = find(blk[pos].rtid, 1, sz, fsz);
            LL res = hsh[fd];
//            printf("pos=%d fsz=%d fd=%lld res=%lld\n", pos, fsz, fd, res);
            cout << 1LL*blk[pos].val*k+res << '\n';
        }else{
            while (fr<ed && (blk[fr].val - blk[fr+1].val) <= x/nd[blk[fr].rtid].cnt){
                x -= 1LL*nd[blk[fr].rtid].cnt*(blk[fr].val - blk[fr+1].val);
                merge(blk[fr+1].rtid, blk[fr].rtid);
                sumblk[fr]=0;
                ++fr;
            }

            if (x > nd[blk[fr].rtid].cnt){
                int tmp=nd[blk[fr].rtid].cnt;
                blk[fr].val -= x/tmp;
                x%=tmp;
            }

            if (x>0){
                int tmprt;
                split(blk[fr].rtid, tmprt, nd[blk[fr].rtid].cnt-x);

                if (fr<ed && blk[fr].val-blk[fr+1].val==1){
                    sumblk[fr] -= x;
                    merge(blk[fr+1].rtid, tmprt);
                }else{
                    sumblk[fr-1] = sumblk[fr]-x;
                    blk[fr-1] = Msg{blk[fr].val, blk[fr].rtid};
                    --blk[fr].val;
                    blk[fr].rtid = tmprt;
                    --fr;
                }
            }
//            for (int i=fr; i<=ed; ++i) printf("i=%d val=%lld rtid=%d sumblk=%d\n", i, blk[i].val, blk[i].rtid, sumblk[i]);
        }
    }

    return 0;
}