#include<bits/stdc++.h>
#define ls Tree[p].lc
#define rs Tree[p].rc
using namespace std;
void read(long long &x) {
    x = 0;
    int f = 1;
    char s = getchar();
    while (s > '9' || s < '0') {
        if (s == '-')
            f = -1;
        s = getchar();
    }
    while (s >= '0' && s <= '9') {
        x = (x << 3) + (x << 1) + (s - '0');
        s = getchar();
    }
    x *= f;
}
void write(long long x) {
    if (x < 0) {
        putchar('-');
        x = (~x) + 1;
    }
    if (x > 9) {
        write(x / 10);
    }
    putchar(x % 10 + '0');
}
const int MAXN=5e5+5;
int n,m;
long long t,k;
long long a[MAXN];
char s[5];
struct Qry{
    long long Time;
    int kth;
    int id;
}Query[MAXN],tmpl[MAXN],tmpr[MAXN];
int x;
__int128 sum[MAXN];
long long Ans[MAXN];
struct Seg{
    int date;
    int lc,rc;
}Tree[MAXN*20];
long long Chu(long long x)
{
    if(x>0)
    {
        return x/k;
    }
    else
    {
        return (x-(x%k+k)%k)/k;
    }
}
long long Mod(long long x)
{
    return ((x%k)+k)%k;
}

int rt;
int cnt_node;
void Insert(int &p,long long l,long long r,long long xg,int op)
{
    if(!p)
    {
        p=++cnt_node;
    }
    Tree[p].date+=op;
    if(l==r)
    {
        return;
    }
    int mid=(l+r)>>1;
    if(xg<=mid)
    {
        Insert(ls,l,mid,xg,op);
    }
    else
    {
        Insert(rs,mid+1,r,xg,op);
    }
}
int Qury(int p,long long l,long long r,long long ql,long long qr)
{
    if(ql>qr)
    {
        return 0;
    }
    if(!p)
    {
        return 0;
    }
    if(l>=ql&&r<=qr)
    {
        return Tree[p].date;
    }
    int mid=(l+r)>>1;
    int Res=0;
    if(ql<=mid)  
    {
        Res+=Qury(ls,l,mid,ql,qr);
    }
    if(qr>mid)
    {
        Res+=Qury(rs,mid+1,r,ql,qr);
    }
    return Res;
}
void solve(long long lv,long long rv,int l,int r,int ql,int qr)
{
    if(ql>qr)
    {
        return;
    }
    if(lv==rv)
    {
        for(int i=ql;i<=qr;i++)
        {
            Ans[Query[i].id]=lv;
        }
        return;
    }
    long long mid=(lv+rv)>>1;
    
    int Key=l-1;
    for(int i=l;i<=r;i++)
    {   
        if(a[i]<=mid)
        {
            Key=i;
        }
        else
        {
            Insert(rt,0,k-1,Mod(a[i]),1);
        }
    }
    __int128 Px=(sum[n]-sum[Key]-((__int128)n-Key)*Chu(mid+1)-Qury(rt,0,k-1,0,Mod(mid+1)-1));
   //cerr<<lv<<" "<<rv<<" "<<l<<" "<<r<<" "<<ql<<" "<<qr<<" "<<mid+1<<endl;
    // cerr<<sum[n]-sum[Key]<<endl;
    // cerr<<Key<<endl;
    // cerr<<sum[n]<<endl;
    // cerr<<Px<<" "<<Qury(rt,0,k-1,0,(mid+1)%k-1)<<endl;

    int pl=0,pr=0;
    for(int i=ql;i<=qr;i++)
    {
        if(Query[i].kth<=((__int128)n-Key)-max((__int128)0,(__int128)Query[i].Time-Px))
        {
            tmpr[++pr]=Query[i];
        }
        else
        {
            tmpl[++pl]=Query[i];
        }
    }
    for(int i=1;i<=pl;i++)
    {
        Query[ql+i-1]=tmpl[i];
    }
    for(int i=1;i<=pr;i++)
    {
        Query[ql+pl+i-1]=tmpr[i];
    }
    solve(lv,mid,l,Key,ql,ql+pl-1);
    for(int i=Key+1;i<=r;i++)
    {
        Insert(rt,0,k-1,Mod(a[i]),-1);
    }
    solve(mid+1,rv,Key+1,r,ql+pl,qr);
}
int main()
{
    // freopen("date.in","r",stdin);
    // freopen("date.out","w",stdout);
   read(n);
   read(m);
   read(k);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
    }
    sort(a+1,a+1+n);
    for(int i=1;i<=n;i++)
    {
        sum[i]=sum[i-1]+Chu(a[i]);
    }
    int cntq=0;
    long long Pt=0;
    while(m--)
    {
        scanf("%s",s);
        if(s[0]=='C')
        {
            scanf("%lld",&t);
            Pt+=t;
        }
        else
        {
            scanf("%d",&x);
            ++cntq;
            Query[cntq]=(Qry){Pt,x,cntq};
        }
    }
    solve(-1e18,1e18,1,n,1,cntq);
    for(int i=1;i<=cntq;i++)
    {   
        printf("%lld\n",Ans[i]);
    }
}

answer.code: In function ‘int main()’:
answer.code:178:9: error: cannot bind non-const lvalue reference of type ‘long long int&’ to a value of type ‘int’
  178 |    read(n);
      |         ^
answer.code:5:22: note:   initializing argument 1 of ‘void read(long long int&)’
    5 | void read(long long &x) {
      |           ~~~~~~~~~~~^
answer.code:179:9: error: cannot bind non-const lvalue reference of type ‘long long int&’ to a value of type ‘int’
  179 |    read(m);
      |         ^
answer.code:5:22: note:   initializing argument 1 of ‘void read(long long int&)’
    5 | void read(long long &x) {
      |           ~~~~~~~~~~~^
answer.code:183:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  183 |         scanf("%lld",&a[i]);
      |         ~~~~~^~~~~~~~~~~~~~
answer.code:194:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  194 |         scanf("%s",s);
      |         ~~~~~^~~~~~~~
answer.code:197:18: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  197 |             scanf("%lld",&t);
      |             ~~~~~^~~~~~~~~~~
answer.code:202:18: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  202 |             scanf("%d",&x);
      |             ~~~~~^~~~~~~~~