#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];
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) {
		//cout << "GGG" << ' ' << lp << ' ' << rp
		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 Seg {
	int root, tot;
	struct SegmentTree {
		int ls, rs, cnt, rt;
		#define ls(x) tree[x].ls
		#define rs(x) tree[x].rs
		#define cnt(x) tree[x].cnt
		#define rt(x) tree[x].rt
	}tree[N * 60];
	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, LL c) {
		if(!p) p = newnode();
		if(lp == rp) {
			Segment::ins(rt(p), 0, K - 1, c);
			cnt(p) = Segment::cnt(rt(p));
			return ;
		}
		LL mid = (lp + rp >> 1);
		if(pos <= mid) ins(ls(p), lp, mid, pos, c);
		else ins(rs(p), mid + 1, rp, pos, c);
		update(p);
	}
	LL query(int p, LL lp, LL rp, int x) {
		if(lp == rp) {
	//		cout << "cnm" << ' ' << lp << ' ' << K << ' ' << x << ' ' << Segment::cnt(rt(p)) << endl; 
			return lp * K + Segment::ask(rt(p), 0, K - 1, x);
		}
		LL mid = (lp + rp >> 1);
		if(cnt(ls(p)) >= x) return query(ls(p), lp, mid, x);
		else return query(rs(p), mid + 1, rp, x - cnt(ls(p)));
	}
	LL Count(int p, LL lp, LL rp, LL pos) {
		if(lp == rp) return cnt(p);
		LL mid = (lp + rp >> 1);
		if(pos <= mid) return Count(ls(p), lp, mid, pos);
		else return Count(rs(p), mid + 1, rp, pos);
	}
	LL Find(int p, LL lp, LL rp, LL pos) { // 找到 <= pos 的最后一个 1， 找不到返回 -1e18 - 1 
	    if(rp <= pos) {
	    	if(cnt(p) == 0) return -1e18 - 1;
	    	else {
	    		if(lp == rp) return lp;
	    		else {
	    			LL mid = (lp + rp >> 1);
	    			if(cnt(rs(p)) > 0) return Find(rs(p), mid + 1, rp, pos);
	    			else return Find(ls(p), lp, mid, pos);
				}
			}
		}
		LL mid = (lp + rp >> 1);
		if(pos <= mid) return Find(ls(p), lp, mid, pos);
		else {
			LL ans = Find(rs(p), mid + 1, rp, pos);
			if(ans == -1e18 - 1) return Find(ls(p), lp, mid, pos);
			else return ans;
		}
	}
	void Crt(int &p, LL lp, LL rp, LL pos, int q) { // 改变 pos 位置的根 
	    if(!p) p = newnode();
		if(lp == rp) {
			rt(p) = q;
			cnt(p) = Segment::cnt(q);
			return ;
		}
		LL mid = (lp + rp >> 1);
		if(pos <= mid) Crt(ls(p), lp, mid, pos, q);
		else Crt(rs(p), mid + 1, rp, pos, q);
		update(p);
	}
	int del(int p, LL lp, LL rp, LL pos) { // 删掉 pos 位置的根并返回编号 
		if(lp == rp) {
			int ans = rt(p);
			rt(p) = 0;
			cnt(p) = 0;
			return ans;
		}
		LL mid = (lp + rp >> 1); int ans;
		if(pos <= mid) ans = del(ls(p), lp, mid, pos);
		else ans = del(rs(p), mid + 1, rp, pos);
		update(p);
		return ans;
	}
	void Merge(LL x, LL y) {
		int p = del(root, -1e18, 1e18, x);
		int q = del(root, -1e18, 1e18, y);
		p = Segment::Merge(p, q, 0, K - 1);
		Crt(root, -1e18, 1e18, x, p);
	}
	void Split(LL pos, LL x) { // 分裂 pos 位置上的树，与 pos - 1 合并 
	//    cout << "GGG" << pos << ' ' << x << endl;
	    int p = del(root, -1e18, 1e18, pos);
	    int q = del(root, -1e18, 1e18, pos - 1LL);
	    int rt;
		Segment::split(p, rt, 0, K - 1, x);
//		cout << "MMM" << ' ' << Segment::cnt(q) << ' ' << Segment::ask(q, 0, K - 1, 1) << endl;
	    q = Segment::Merge(q, rt, 0, K - 1);
//		cout << "CNMCNM" << ' ' << Segment::cnt(rt1) << ' ' << ' ' << Segment::cnt(rt2) << ' ' << Segment::cnt(q) <<' ' << Segment::ask(rt2, 0, K - 1, 1) << ' ' << Segment::ask(q, 0, K - 1, 3) << endl;
	    Crt(root, -1e18, 1e18, pos, p);
	    Crt(root, -1e18, 1e18, pos - 1, q);
	}
}
void move(LL x) { // 将最大的减少K  x次    方法是每次找到最后一个1，看能不能和前面那个合并，然后在分裂一次 
	while(x) {
		LL lst = Seg::Find(Seg::root, -1e18, 1e18, 1e18); // 找到 
		LL pre = Seg::Find(Seg::root, -1e18, 1e18, lst - 1LL);
		LL ct = Seg::Count(Seg::root, -1e18, 1e18, lst);
	//	cout << "LLL" << lst << ' ' << pre << ' ' << ct << endl;
		if(pre >= -1e18 && (Int)(lst - pre) * ct <= x) {
			x -= (lst - pre) * ct;
			Seg::Merge(pre, lst);
			continue;
		}
		LL step = x / ct; // 整体移动 step 
		int rt = Seg::del(Seg::root, -1e18, 1e18, lst);
		Seg::Crt(Seg::root, -1e18, 1e18, lst - step, rt); // 改变根 
		x -= ct * step; // 还剩下的需要分裂 
	//	cout << "HHH" << x << endl;
		if(x) Seg::Split(lst - step, x); // 分裂 
		x = 0;
	}
}
int main() {
	scanf("%d%d%lld", &n, &m, &K);
	for(int i = 1; i <= n; i ++ ) {
		scanf("%lld", &a[i]);
		Seg::ins(Seg::root, -1e18, 1e18, (a[i] / K), a[i] % K);
	}
	cout << "KKK" << endl;
	for(int i = 1; i <= m; i ++ ) {
		char opt; LL x;
		scanf("\n%c%lld", &opt, &x);
		if(opt == 'C') { // 修改 
			move(x); // 移动 x 步 
		} 
		else { // 查询第x大 
			printf("%lld\n", Seg::query(Seg::root, -1e18, 1e18, n - x + 1));
		}
	}
	return 0;
}
/*
3 5 5
7 3 9
A 3
C 1
A 2
C 2
A 3
*/