#include<cstdio>
#include<iostream>
#include<cctype>
#include<vector>
#include<algorithm>
#define int long long
#define RI register int
#define CI const int&
using namespace std;
const int N=500005;
#define Tp template <typename T>
class FileInputOutput
{
    private:
        static const int S=1<<21;
        #define tc() (A==B&&(B=(A=Fin)+fread(Fin,1,S,stdin),A==B)?EOF:*A++)
        #define pc(ch) (Ftop!=Fend?*Ftop++=ch:(fwrite(Fout,1,S,stdout),*(Ftop=Fout)++=ch))
        char Fin[S],Fout[S],*A,*B,*Ftop,*Fend; int pt[30];
    public:
        inline FileInputOutput(void) { Ftop=Fout; Fend=Fout+S; }
        Tp inline void read(T& x)
        {
            x=0; char ch; while (!isdigit(ch=tc()));
            while (x=(x<<3)+(x<<1)+(ch&15),isdigit(ch=tc()));
        }
        inline void get_char(char& ch)
        {
        	while (!isalpha(ch=tc()));
        }
        Tp inline void write(T x,const char ch='\n')
        {
        	if (x<0) x=-x,pc('-');
            RI ptop=0; while (pt[++ptop]=x%10,x/=10);
            while (ptop) pc(pt[ptop--]+48); pc(ch);
        }
        inline void flush(void)
        {
            fwrite(Fout,1,Ftop-Fout,stdout);
        }
        #undef tc
        #undef pc
}F;
int n,m,k,a[N],x,rt[N],sz[N],idx; vector <int> rst,module;
class Segment_Tree
{
	private:
		struct segment
		{
			int ch[2],sz;
		}O[N*20];
	public:
		inline void insert(int& x,CI pos,CI l=0,CI r=module.size()-1)
		{
			if (!x) x=++idx; ++O[x].sz; if (l==r) return; int mid=l+r>>1;
			if (pos<=mid) insert(O[x].ch[0],pos,l,mid); else insert(O[x].ch[1],pos,mid+1,r);
		}
		inline int merge(int x,int y,CI l=0,CI r=module.size()-1)
		{
			if (!x||!y) return x|y; if (l==r) return O[x].sz+=O[y].sz,x; int mid=l+r>>1;
			O[x].ch[0]=merge(O[x].ch[0],O[y].ch[0],l,mid);
			O[x].ch[1]=merge(O[x].ch[1],O[y].ch[1],mid+1,r);
			O[x].sz=O[O[x].ch[0]].sz+O[O[x].ch[1]].sz; return x;
		}
		inline int find_kth(CI x,CI rk,CI l=0,CI r=module.size()-1)
		{
			if (l==r) return module[l]; int mid=l+r>>1;
			if (rk<=O[O[x].ch[1]].sz) return find_kth(O[x].ch[1],rk,mid+1,r);
			return find_kth(O[x].ch[0],rk-O[O[x].ch[1]].sz,l,mid);
		}
		inline int query(CI x,CI lim,CI grt,CI l=0,CI r=module.size()-1)
		{
			if (!lim||module[r]<=grt) return 0; if (grt<module[l]) return O[x].sz; int mid=l+r>>1;
			if (lim<=O[O[x].ch[1]].sz) return query(O[x].ch[1],lim,grt,mid+1,r);
			return query(O[x].ch[1],O[O[x].ch[1]].sz,grt,mid+1,r)+query(O[x].ch[0],lim-O[O[x].ch[1]].sz,grt,l,mid);
		}
}SEG;
signed main()
{
	//freopen("I.in","r",stdin); freopen("I.out","w",stdout);
	RI i; for (F.read(n),F.read(m),F.read(k),i=1;i<=n;++i)
	F.read(a[i]),rst.push_back(a[i]/k),module.push_back(a[i]%k);
	sort(rst.begin(),rst.end()); rst.erase(unique(rst.begin(),rst.end()),rst.end());
	sort(module.begin(),module.end()); module.erase(unique(module.begin(),module.end()),module.end());
	for (i=1;i<=n;++i)
	{
		int id=lower_bound(rst.begin(),rst.end(),a[i]/k)-rst.begin(); ++sz[id];
		SEG.insert(rt[id],lower_bound(module.begin(),module.end(),a[i]%k)-module.begin());
	}
	vector <int> pfx(rst.size()); pfx[0]=sz[0];
	for (i=1;i<rst.size();++i) pfx[i]=pfx[i-1]+sz[i];
	int pos=0,id=rst.size()-1; for (i=1;i<=m;++i)
	{
		char opt; F.get_char(opt); F.read(x);
		if (opt=='C')
		{
			while (x>0)
			{
				if (pos+x<sz[id]) { pos+=x; x=0; break; }
				x-=sz[id]-pos; --rst[id]; pos=0;
				if (id>0)
				{
					int steps=(rst[id]-rst[id-1])*sz[id];
					if (steps<=x)
					{
						x-=steps; pfx[id-1]+=sz[id]; sz[id-1]+=sz[id];
						rt[id-1]=SEG.merge(rt[id-1],rt[id]); --id;
					} else
					{
						rst[id]-=x/sz[id]; pos=x%sz[id]; x=0;
					}
				} else
				{
					rst[0]-=x/n; pos=x%n; x=0;
				}
			}
		} else
		{
			if (x<=sz[id]-pos)
			{
				F.write(rst[id]*k+SEG.find_kth(rt[id],pos+x)); continue;
			} else x-=(sz[id]-pos);
			if (id>0&&rst[id]-1==rst[id-1]&&x<=pos+sz[id-1])
			{
				int l=0,r=k-1,mid,ret;
				while (l<=r)
				{
					mid=l+r>>1;
					if (SEG.query(rt[id],pos,mid)+SEG.query(rt[id-1],sz[id-1],mid)<x) ret=mid,r=mid-1; else l=mid+1;
				}
				F.write(rst[id-1]*k+ret); continue;
			}
			if (x<=pos)
			{
				F.write((rst[id]-1)*k+SEG.find_kth(rt[id],x)); continue;
			} else x-=pos;
			int l=0,r=id-1,mid,ret;
			while (l<=r)
			{
				mid=l+r>>1;
				if (pfx[id-1]-pfx[mid]<x) ret=mid,r=mid-1; else l=mid+1;
			}
			F.write(rst[ret]*k+SEG.find_kth(rt[ret],x-(pfx[id-1]-pfx[ret])));
		}
	}
	return F.flush(),0;
}