#include<bits/stdc++.h>
#define Gc() getchar()
#define Me(x,y) memset(x,y,sizeof(x))
#define Mc(x,y) memcpy(x,y,sizeof(x))
#define d(x,y) ((m)*(x-1)+(y))
#define R(n) (rnd()%(n)+1)
#define Pc(x) putchar(x)
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define eb emplace_back
using namespace std;using ll=long long;using db=double;using lb=long db;using ui=unsigned;using ull=unsigned long long;using pii=pair<int,int>;
const int N=5e5+5,M=N*4+5,K=(1<<25)+5,mod=998244353,Mod=mod-1;const db eps=1e-9;const int INF=1e9+7;mt19937 rnd(time(0));
int n,m;ll k,A[N];
int l[N],r[N],siz[N],rd[N],cnt;ll val[N],g[N];
void Pg(int v,ll w){if(v) val[v]+=w,g[v]+=w;}
void P(int v){if(g[v]) Pg(l[v],g[v]),Pg(r[v],g[v]),g[v]=0;}
void up(int v){siz[v]=siz[l[v]]+siz[r[v]]+1;}
void split1(ll x,int v,int &a,int &b){
	if(!v){a=b=0;return;}P(v);
	if(x>=val[v]) a=v,split1(x,r[v],r[a],b);
	else b=v,split1(x,l[v],a,l[b]);
	up(v);
}
void split2(int x,int v,int &a,int &b){
	if(!v){a=b=0;return;}P(v);
	if(x>=siz[l[v]]+1) a=v,split2(x-siz[l[v]]-1,r[v],r[a],b);
	else b=v,split2(x,l[v],a,l[b]);
	up(v);
}
ll qry(int x,int v){
	P(v);
	if(x==siz[r[v]]+1) return val[v];
	if(x>siz[r[v]]+1) return qry(x-siz[r[v]]-1,l[v]);
	else return qry(x,r[v]);
}
int newn(ll x){siz[++cnt]=1;rd[cnt]=rnd();val[cnt]=x;return cnt;}
int merge(int x,int y){
	if(!x||!y) return x|y;P(x);P(y);
	if(rd[x]<rd[y]) return r[x]=merge(r[x],y),up(x),x;
	else return l[y]=merge(x,l[y]),up(y),y;
}
ll qi(int x){while(l[x]) P(x),x=l[x];return val[x];}
ll qx(int x){while(r[x]) P(x),x=r[x];return val[x];}
int rt;
using LL=__int128;
void Solve(){
	int i,j;scanf("%d%d%lld",&n,&m,&k);
	for(i=1;i<=n;i++) scanf("%lld",&A[i]);
	sort(A+1,A+n+1);
	int R=n-1;rt=newn(A[n]);
	while(m--){
		char c;c=Gc();while(c<'A'||c>'Z') c=Gc();
		ll x;scanf("%lld",&x);
		if(c=='C'){
			while(R){
				LL w=(LL)(qi(rt)-A[R])/k*(n-R);
				if(w>x) break;
				Pg(rt,-(qi(rt)-A[R])/k*k);x-=w;
				int r1,r2;split1(A[R]+k-1,rt,r1,r2);
				if(siz[r2]<=x){
					Pg(r2,-k);x-=siz[r2];
					rt=merge(merge(newn(A[R]),r2),r1);
					R--;
				}else{rt=merge(r1,r2);break;}
			}
			ll w=x/(n-R);
			Pg(rt,-w*k);x-=w*(n-R);
			int r1,r2;split2((n-R)-x,rt,r1,r2);
			Pg(r2,-k);rt=merge(r2,r1);
		}else{
			printf("%lld\n",x<=n-R?qry(x,rt):A[n-x+1]);
		}
	}
}
int main
	int t=1;
	// scanf("%d",&t);
	while(t--) Solve();
	cerr<<clock()*1.0/CLOCKS_PER_SEC<<'\n';
}

answer.code:78:9: error: expected initializer before ‘int’
   78 |         int t=1;
      |         ^~~
answer.code:80:9: error: expected unqualified-id before ‘while’
   80 |         while(t--) Solve();
      |         ^~~~~
answer.code:81:9: error: ‘cerr’ does not name a type
   81 |         cerr<<clock()*1.0/CLOCKS_PER_SEC<<'\n';
      |         ^~~~
answer.code:82:1: error: expected declaration before ‘}’ token
   82 | }
      | ^
answer.code: In function ‘void Solve()’:
answer.code:49:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   49 |         int i,j;scanf("%d%d%lld",&n,&m,&k);
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~~~
answer.code:50:32: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   50 |         for(i=1;i<=n;i++) scanf("%lld",&A[i]);
      |                           ~~~~~^~~~~~~~~~~~~~
answer.code:55:27: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   55 |                 ll x;scanf("%lld",&x);
      |                      ~~~~~^~~~~~~~~~~