#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=5e5+11;
int n,m;
LL k;
LL a[N];
#define ls(x) (x<<1)
#define rs(x) ((x<<1)|1)
#define mid ((l+r)>>1)
int sum[N<<2];
void push_up(int now){
  sum[now]=sum[ls(now)]+sum[rs(now)];
}
void insert(int l,int r,int now,int index,int cnt){
  if(l==r){
    sum[now]+=cnt;
    return;
  }
  if(index<=mid){
    insert(l,mid,ls(now),index,cnt);
  }
  else{
    insert(mid+1,r,rs(now),index,cnt);
  }
  push_up(now);
}
int interval_sum(int l,int r,int now,int st,int en){
  if(st<=l&&r<=en){
    return sum[now];
  }
  int ret=0;
  if(st<=mid){
    ret+=interval_sum(l,mid,ls(now),st,en);
  }
  if(en>mid){
    ret+=interval_sum(mid+1,r,rs(now),st,en);
  }
  return ret;
}
pair<int,int> get_kth(int l,int r,int now,int st,int en,int k){
  if(l==r){
    if(k<=sum[now])
      return make_pair(l,k);
    return make_pair(-1,sum[now]);
  }
  if(st<=l&&r<=en){
    if(sum[now]<k){
      return make_pair(-1,sum[now]);
    }
    if(sum[rs(now)]>=k){
      return get_kth(mid+1,r,rs(now),st,en,k);
    }
    return get_kth(l,mid,ls(now),st,en,k-sum[rs(now)]);
  }
  pair<int,int>p=make_pair(-1,sum[now]);
  if(en>mid){
    p=get_kth(mid+1,r,rs(now),st,en,k);
  }
  if(p.first==-1&&st<=mid){
    p=get_kth(l,mid,ls(now),st,en,k-p.second);
  }
  return p;
}
#undef ls
#undef rs
#undef mid
map<LL,int> mp;
LL inv[N];
namespace BF{
  LL a[N];
  void C(LL t){
    while(t--){
      int index=1;
      for(int i=2;i<=n;++i){
        if(a[i]>a[index]){
          index=i;
        }
      }
      a[index]-=k;
    }
  }
  LL A(LL x){
    static LL b[N];
    for(int i=1;i<=n;++i)b[i]=a[i];
    sort(b+1,b+n+1);
    return b[n-x+1];
  }
}
int main(){
  //freopen("i.in","r",stdin);
  scanf("%d%d%lld",&n,&m,&k);
  set<LL> remSet;
  for(int i=1;i<=n;++i){
    scanf("%lld",&a[i]);
    BF::a[i]=a[i];
    remSet.insert(a[i]%k);
  }
  int rTail=0;
  for(LL r:remSet){
    ++rTail;
    mp[r]=rTail;
    inv[rTail]=r;
  }
  sort(a+1,a+n+1);
  int setSize=1;
  int aTail=n-1;
  insert(1,rTail,1,mp[a[n]%k],1);
  LL p=a[n]/k;
  int front=0;
  while(m--){
    char s[10];
    scanf("%s",s);
    if(s[0]=='C'){
      LL t;
      scanf("%lld",&t);
      //BF::C(t);
      while(aTail>=1){
        if((__int128_t)p*setSize+front-(__int128_t)a[aTail]/k*setSize<=(__int128_t)t){
          t-=(__int128_t)p*setSize+front-(__int128_t)a[aTail]/k*setSize;
          front=0;
          p=a[aTail]/k;
          insert(1,rTail,1,mp[a[aTail]%k],1);
          --aTail;
          ++setSize;
        }
        else{
          break;
        }
      }
      __int128_t pot=(__int128_t)p*setSize+front-t;      
      front=(pot%setSize+setSize)%setSize;
      p=(pot-front)/setSize;
    }
    else{
      int x;
      scanf("%d",&x);
      LL ans=-1;
      if(x>setSize){
        ans=a[aTail-x+setSize+1];
      }
      else{
        LL r=-1;
        if(front>=x){
          pair<int,int> tmp=get_kth(1,rTail,1,1,rTail,setSize-front+x);
          r=inv[tmp.first];
          ans=(p+1)*k+r;
        }
        else{
          pair<int,int> tmp=get_kth(1,rTail,1,1,rTail,x-front);
          r=inv[tmp.first];
          ans=p*k+r;
        }
      }
      //LL jury=BF::A(x);
      // if(jury!=ans){
      //   printf("WA:jury=%lld, ans=%lld\n",jury,ans);
      //   assert(0);
      // }
      printf("%lld\n",ans);
    }
  }
  return 0;
}