#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e5+5;
struct node{
    int p,y;
}a[N];
bool cmd(node xx,node yy){
    if(xx.p==yy.p)return xx.y>yy.y;
    return xx.p>yy.p;
}
class sgt{
    public:
        int n,cnt,root;
        vector<int> ls,rs,sum;
        sgt(int _n = 0){
            root = 1;
            n = _n; cnt = 1;
            ls.resize(30 * n + 1,0);
            rs.resize(30 * n + 1,0);
            sum.resize(30 * n + 1,0);
        }
        #define mid ((l + r ) >> 1)
        void update(int &pos,int l,int r,int x,int v){
            if(!pos) pos = ++cnt;
            sum[pos] += 1;
            if(l == r) return;
            if(x <= mid)    
                update(ls[pos],l,mid,x,v);
            else
                update(rs[pos],mid+1,r,x,v);
        }
        pair<int,pair<int,int>> query(int pos,int l,int r,int ql,int qr,int rnk){
            if(ql <= l && r <= qr){
                if(sum[pos] < rnk)
                    return make_pair(0,make_pair(sum[pos],0));
            }
            if(l == r){
                if(sum[pos] >= rnk)
                    return make_pair(l,make_pair(sum[pos],rnk));
                else
                    return make_pair(0,make_pair(sum[pos],0));
            }
            pair<int,pair<int,int>> ansl,ansr;
            ansl = ansr = make_pair(0,make_pair(0,0));
            if(ql <= mid){
                ansl = query(ls[pos],l,mid,ql,qr,rnk);
            }
            if(ansl.first)
                return ansl;
            else
                rnk -= ansl.second.first;
            if(qr > mid){
                ansr = query(rs[pos],mid+1,r,ql,qr,rnk);
            }
            return ansr;
        }
        int size(){
            return sum[1];
        }
        pair<int,pair<int,int>> Query(int l,int r,int k){
            auto res = query(root,0,n,l,r,k);
            // if(!res.first) assert(0);
            return res;
        }
        void Upd(int x,int v = 1){
            update(root,0,n,x,v);
        }
}p[2];
void addtree(int idx,int l,int r,int x){
    idx--;
    p[idx].Upd(x);
}
pair<int,pair<int,int>> findtree(int idx,int l,int r,int rnk){
    idx--;
    return p[idx].Query(l,r,rnk);
}
signed main(){
    #ifdef NICEGUODONG
        freopen("data.in","r",stdin);
    #endif
    ios::sync_with_stdio(0);
    int n,m,k;
    cin>>n>>m>>k;
    for(int i=1; i<=n; i++){
        int x;
        cin>>x;
        a[i].p=x/k;
        a[i].y=x%k;
    }
    p[0] = sgt(k);
    p[1] = sgt(k);
    sort(a+1,a+n+1,cmd);
    int sz1=0,sz2=0,now1,now2,nowp=a[1].p;
    // return 0;
    for(int i=1; i<=n; i++){
        if(a[i].p==a[1].p)addtree(1,0,k-1,a[i].y),sz1++,now1=i;
        if(a[i].p>=a[1].p-1)addtree(2,0,k-1,a[i].y),sz2++,now2=i;
    }
    int sum=0;
    for(int i=1; i<=m; i++){
        char ch;
        cin>>ch;
        if(ch=='A'){
            int x;
            cin>>x;
            // cout<<sz1<<' '<<sz2<<endl;
            if(x<=sz1-sum){
                auto yu=findtree(1,0,k-1,sz1-sum-x+1);
                cout<<k*nowp+yu.first<<endl;
            }else{
                if(x>sz2){
                    cout<<a[x].p*k+a[x].y<<endl;
                    continue;
                }
                if(sz2>=(x-(sz1-sum))){
                    if(sum==0){
                        cout<<a[x].p*k+a[x].y<<endl;
                        continue;
                    }
                    auto yu=findtree(2,0,k-1,sz2-(x-(sz1-sum))+1);
                    auto to=findtree(1,0,k-1,sz1-sum+1);
                    // cout<<(sz2-(x-(sz1-sum))+1)<<' '<<yu.first<<endl;
                    if((yu.first>to.first)||(yu.first==to.first)&&(yu.second.second>=to.second.second))cout<<k*(nowp-1)+yu.first<<endl;
                    else cout<<a[x].p*k+a[x].y<<endl;
                }else cout<<a[x].p*k+a[x].y<<endl;
            }
        }else{
            int t;
            cin>>t;
            sum+=t;
            // cout<<'#'<<sum<<endl;
            if(now1<n){
                if(sum>=sz1*(nowp-a[now1+1].p)){
                    sum-=sz1*(nowp-a[now1+1].p);
                    nowp=a[now1+1].p;
                }
            }else{
                if(sum>=sz1){
                    int delt=sum/sz1;
                    nowp-=delt;
                    sum-=delt*sz1;
                }
            }
            while(now1<n&&a[now1+1].p>=nowp){
                now1++;
                addtree(1,0,k-1,a[now1].y);
                sz1++;
            }
            while(now2<n&&a[now2+1].p>=nowp-1){
                now2++;
                addtree(2,0,k-1,a[now2].y);
                sz2++;
            }
        }
    } 
    return 0;
}