#include<bits/stdc++.h>
using namespace std;
const int N = 5e5 + 10;
typedef long long LL;
typedef __int128 Int;
int n, m;
LL K, a[N], Lim;
struct IO{
    static const int S=1<<21;
    char buf[S],*p1,*p2;int st[105],Top;
    ~IO(){clear();}
    inline void clear(){fwrite(buf,1,Top,stdout);Top=0;}
    inline void pc(const char c){Top==S&&(clear(),0);buf[Top++]=c;}
    inline char gc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}
    inline IO&operator >> (char&x){while(x=gc(),x==' '||x=='\n'||x=='\r');return *this;}
    template<typename T>inline IO&operator >> (T&x){
        x=0;bool f=0;char ch=gc();
       while(!isdigit(ch)){if(ch=='-') f^=1;ch=gc();}
        while(isdigit(ch)) x=(x<<3)+(x<<1)+ch-'0',ch=gc();
        f?x=-x:0;return *this;
    }
    inline IO&operator << (const char c){pc(c);return *this;}
    template<typename T>inline IO&operator << (T x){
        if(x<0) pc('-'),x=-x;
        do{st[++st[0]]=x%10,x/=10;}while(x);
        while(st[0]) pc('0'+st[st[0]--]);return *this;
    }
}fin,fout;
namespace Segment {
	struct SegmentTree {
		int ls, rs, cnt;
		#define ls(x) tree[x].ls
		#define rs(x) tree[x].rs
		#define cnt(x) tree[x].cnt
	}tree[N * 60];
	int tot;
	int newnode() {return ++ tot;}
	void update(int p) {
		cnt(p) = cnt(ls(p)) + cnt(rs(p));
	}
	void ins(int &p, LL lp, LL rp, LL pos) {
		if(!p) p = newnode();
		if(lp == rp) {
			cnt(p) ++;
			return ;
		}
		LL mid = (lp + rp >> 1);
		if(pos <= mid) ins(ls(p), lp, mid, pos);
		else ins(rs(p), mid + 1, rp, pos);
		update(p);
	}
	LL ask(int p, LL lp, LL rp, int x) {
		if(lp == rp) return lp;
		LL mid = (lp + rp >> 1);
		if(cnt(ls(p)) >= x) return ask(ls(p), lp, mid, x);
		else return ask(rs(p), mid + 1, rp, x - cnt(ls(p)));
 	}
 	int Merge(int p, int q, LL lp, LL rp) {
 		if(!p || !q) return p ^ q;
 		if(lp == rp) {
 			cnt(p) += cnt(q);
 			return p;
		}
		LL mid = (lp + rp >> 1);
		ls(p) = Merge(ls(p), ls(q), lp, mid);
		rs(p) = Merge(rs(p), rs(q), mid + 1, rp);
		update(p);
		return p;
	}
	void split(int &p, int &q, LL lp, LL rp, LL c) {
		if(!p) return ;
		if(lp == rp) {
			if(cnt(p) == c) {
				q = p; p = 0;
				return ;
			}
			else {
				int u = newnode();
				cnt(u) = c; cnt(p) -= c;
			    q = u;
				return ;
			}
		}
		if(!q) q = newnode();
		LL mid = (lp + rp >> 1);
		if(cnt(rs(p)) >= c) split(rs(p), rs(q), mid + 1, rp, c);
		else {
			rs(q) = rs(p); rs(p) = 0;
			split(ls(p), ls(q), lp, mid, c - cnt(rs(q)));
		}
		update(p); update(q);
	}
}
namespace Fhq { // 改成平衡树   空间线性 
	int root, tot;
	int rt1, rt2, rt3;
	mt19937_64 rnd(time(0));
	struct Node {
		int son[2];
		int cnt, sz, rt; // 数量， 根 
		LL val, w; // 数值  随机权重 
	}t[N * 10];
	int newnode(LL v) {
		tot ++;
		t[tot].val = v;
		t[tot].w = rnd();
		return tot;
	}
	void update(int p) {
		t[p].sz = t[t[p].son[0]].sz + t[t[p].son[1]].sz + t[p].cnt;
	}
	int Merge(int p, int q) {
	    if(!p || !q) return p ^ q;	
	    if(t[p].w > t[q].w) {
	    	t[p].son[1] = Merge(t[p].son[1], q);
	    	update(p);
	    	return p;
		}
		else {
			t[q].son[0] = Merge(p, t[q].son[0]);
			update(q);
			return q;
		}
	}
	void split(int p, int &x, int &y, LL lim) {		
		if(!p) {x = y = 0; return ;}
		if(t[p].val <= lim) x = p, split(t[p].son[1], t[p].son[1], y, lim);
		else y = p, split(t[p].son[0], x, t[p].son[0], lim);
		update(p);
	}
	void ins(int p, LL v) {
		Segment::ins(t[p].rt, 0, K - 1, v);
		t[p].cnt ++; t[p].sz ++;
	}
	void add(LL v1, LL v2) { // 插入一个 
		split(root, rt1, rt2, v1);
		split(rt1, rt1, rt3, v1 - 1);
		if(!rt3) rt3 = newnode(v1);
		ins(rt3, v2);
		root = Merge(Merge(rt1, rt3), rt2);
	}
	LL query(int p, int x) { // 查询第 x 个 
	    if(!p) return 0;
		if(t[t[p].son[0]].sz >= x) return query(t[p].son[0], x);
		else if(t[t[p].son[0]].sz + t[p].cnt >= x) return 1LL * t[p].val * K + Segment::ask(t[p].rt, 0, K - 1, x - t[t[p].son[0]].sz);
		else return query(t[p].son[1], x - (t[t[p].son[0]].sz + t[p].cnt));
	}
	LL Pre(LL x) {
		split(root, rt1, rt2, x);
		int p = rt1;
		while(t[p].son[1]) p = t[p].son[1];
		root = Merge(rt1, rt2);
		return p == 0 ? -2e18 : t[p].val;
 	}
 	LL Count(int p, LL x) {
 		if(!p) return 0;
 		if(t[p].val == x) return t[p].cnt;
 		if(t[p].val > x) return Count(t[p].son[0], x);
 		else return Count(t[p].son[1], x);
	}
	int del(LL x) { // 删去值为 x 的节点，并且返回它的根 
		split(root, rt1, rt2, x);
		split(rt1, rt1, rt3, x - 1); // 删掉 rt3 的根 
		root = Merge(rt1, rt2);
		return t[rt3].rt;
	}
	void Crt(LL x, int p) {
		split(root, rt1, rt2, x);
		split(rt1, rt1, rt3, x - 1);
		if(!rt3) rt3 = newnode(x);
		t[rt3].rt = p; 
		t[rt3].sz = t[rt3].cnt = Segment::cnt(p);
		root = Merge(Merge(rt1, rt3), rt2);
	}
	void Mg(LL x, LL y) { // 把 y 删掉， 合并到 x 里面 
		int p = del(x);
		int q = del(y);
		p = Segment::Merge(p, q, 0, K - 1);
		Crt(x, p);
	}
	void Sp(LL x, LL c) {
		int p = del(x), q = del(x - 1);
		int Rt = 0;
		Segment::split(p, Rt, 0, K - 1, c);
		Crt(x, p); 
		q = Segment::Merge(q, Rt, 0, K - 1);
		Crt(x - 1, q);
	}
	void dfs(int x) {
		if(!x) return ;
		dfs(t[x].son[0]);
		printf("%lld ", t[x].val);
		dfs(t[x].son[1]);
	}
}
void move(LL x) { // 将最大的减少K  x次    方法是每次找到最后一个1，看能不能和前面那个合并，然后在分裂一次 
	int cnt = 0;
	while(x) {
		LL lst = Fhq::Pre(1e18); // 找到 
		LL pre = Fhq::Pre(lst - 1);
		LL ct = Fhq::Count(Fhq::root, lst);
		cnt ++;
		if(cnt > n - 10) {
			printf("%lld %lld %lld\n", pre, lst, ct);
		}
		if(cnt > n) {
			puts("cnm");
			exit(0);
		}
		if(pre >= -1e18 && (Int)(lst - pre) * ct <= x) {
			x -= (lst - pre) * ct;
			Fhq::Mg(pre, lst);
			continue;
		}
		LL step = x / ct; // 整体移动 step 
		int rt = Fhq::del(lst);
		Fhq::Crt(lst - step, rt); // 改变根 
		x -= ct * step; // 还剩下的需要分裂 
		if(x) Fhq::Sp(lst - step, x); // 分裂
		x = 0;
	}
}
int main() {
	fin >> n >> m >> K;
	for(int i = 1; i <= n; i ++ ) {
		fin >> a[i];
		Fhq::add(a[i] / K, a[i] % K);
	}
	for(int i = 1; i <= m; i ++ ) {
		char opt; LL x;
		opt = fin.gc(); fin >> x;
		if(opt == 'C') { // 修改 
			move(x); // 移动 x 步 
		} 
		else { // 查询第x大 
		    fout << Fhq::query(Fhq::root, n - x + 1); fout.pc('\n');
	//		printf("%lld\n", Fhq::query(Fhq::root, n - x + 1));
		}
	}
	return 0;
}
/*
3 5 5
7 3 9
A 3
C 1
A 2
C 2
A 3
*/