# include <bits/stdc++.h>

using namespace std ;

int n , m ;
typedef long long ll ;
ll k ;
ll a[500005] ;
struct node
{
	int l , r ;
	int lson , rson , sum ;
} seg[10000005] ;
int idx ;
void pushup( int id )
{
	seg[id].sum = seg[seg[id].lson].sum + seg[seg[id].rson].sum ;
}
void update( int id , int x , int v )
{
	if ( seg[id].l == x && seg[id].r == x ) 
	{
		seg[id].sum += v ;
		return ;
	}
	int mid = ( seg[id].l + seg[id].r ) >> 1 ;
	if ( x <= mid )
	{
		if ( ! seg[id].lson ) 
		{
			seg[id].lson = ++idx ;
			seg[idx].l = seg[id].l  , seg[idx].r = mid ;
		}
		update( seg[id].lson , x , v ) ;
	}
	else
	{
		if ( ! seg[id].rson )
		{
			seg[id].rson = ++idx ;
			seg[idx].l = mid + 1 , seg[idx].r = seg[id].r ;
		}
		update( seg[id].rson , x , v ) ;
	}
	pushup( id ) ;
}
int query( int id , int l , int r ) // 查区间和 
{
	if ( l > r ) return 0 ;
	if ( ! id ) return 0 ;
	if ( l <= seg[id].l && seg[id].r <= r ) return seg[id].sum ;
	int mid = ( seg[id].l + seg[id].r ) >> 1 , ans = 0 ;
	if ( l <= mid ) 
	{
		ans += query( seg[id].lson , l , r ) ;
	}
	if ( mid + 1 <= r )
	{
		ans += query( seg[id].rson , l , r ) ;
	}
	return ans ;
}
int merge( int x , int y )
{
	if ( ! x || ! y ) return x + y ;
	if ( seg[x].l == seg[x].r )
	{
		seg[x].sum += seg[y].sum ;
		return x ;
	}
	seg[x].lson = merge( seg[x].lson , seg[y].lson ) ;
	seg[x].rson = merge( seg[x].rson , seg[y].rson ) ;
	pushup( x ) ;
	return x ;
}
int qkth( int id , int k )
{
	if ( ! id ) return 0 ;
	if ( seg[id].l == seg[id].r ) return seg[id].l  ;
	if ( k <= seg[seg[id].rson].sum ) return qkth( seg[id].rson , k ) ;
	return qkth( seg[id].lson , k - seg[seg[id].rson].sum ) ;  
}
int qkth2( int id1 , int id2 , int k )
{
	if ( ! id1 && ! id2 ) return 0 ;
	if ( seg[id1].l == seg[id1].r ) return seg[id1].l  ;
	if ( k <= seg[seg[id2].rson].sum + seg[seg[id1].rson].sum ) return qkth2( seg[id1].rson , seg[id2].rson , k ) ;
	return qkth2( seg[id1].lson , seg[id2].lson , k - ( seg[seg[id2].rson].sum + seg[seg[id1].rson].sum ) ) ;  
}
int rt[500005] ;
ll nums[500005] , cnt ;
struct qe
{
	bool tp ;
	ll v ;
} q[500005] ;
const ll INF = 1e18 ;
int main()
{
	scanf("%d%d" , &n , &m) ;
	scanf("%lld" , &k) ;
	for ( int i = 1 ; i <= n ; i++ ) 
	{
		scanf("%lld" , a + i) ;
		nums[++ cnt] = a[i] / k ;
	}
	sort( a + 1 , a + n + 1 ) ;
	for ( int i = 1 ; i <= m ; i++ )
	{
		char ch ;
		cin >> ch ;
		scanf("%lld" , &q[i].v) ;
		q[i].tp = ( ch == 'C' ) ;
	}
	sort( nums + 1 , nums + cnt + 1 ) ;
	cnt = unique( nums + 1 , nums + cnt + 1 ) - nums - 1 ;
	for ( int i = 1 ; i <= cnt ;i ++ ) 
	{
		rt[i] = ++idx ;
		seg[idx].l = 0 , seg[idx].r = k - 1 ;
	}
	for ( int i = 1 ; i <= n ; i++ )
	{
		int np = lower_bound( nums + 1 , nums + cnt + 1 , a[i] / k ) - nums ;
		update( rt[np] , a[i] % k , 1 ) ;
	}
	nums[0] = -INF ;
	int nst = cnt ;
	ll nv = nums[cnt] , add = 0 ;
	for ( int i = 1 ; i <= m ; i++ )
	{
		if ( q[i].tp == 1 )
		{
			add += q[i].v ;
			while ( true )
			{
				ll dv = add / seg[rt[nst]].sum ;
				if ( nv - dv > nums[nst - 1] ) 
				{
					nv -= dv , add -= dv * seg[rt[nst]].sum ;
					break ;
				}
				else
				{
					add -= ( nv - nums[nst - 1] ) * seg[rt[nst]].sum ;
					rt[nst - 1] = merge( rt[nst] , rt[nst - 1] ) ;
					nv = nums[nst - 1] ;
					nst-- ;
				}
			}
		}
		else
		{
			int x = q[i].v ;
			if ( nv - nums[nst - 1] > 1 )
			{
				if ( x > seg[rt[nst]].sum )
				{
					printf("%lld\n" , a[n - x + 1]) ;
				}
				else
				{
					if ( x <= seg[rt[nst]].sum - add )
					{
						printf("%lld\n" , nv * k + qkth( rt[nst] , add + x )) ;
					}
					else
					{
						printf("%lld\n" , ( nv - 1 ) * k + qkth( rt[nst] , x - ( seg[rt[nst]].sum - add ) ) ) ;
					}
				}
			}
			else
			{
				if ( x > seg[rt[nst]].sum + seg[rt[nst - 1]].sum )
				{
					printf("%lld\n" , a[n - x + 1]) ;
				}
				else
				{
					if ( x <= seg[rt[nst]].sum - add )
					{
						printf("%lld\n" , nv * k + qkth( rt[nst] , add + x )) ;
					}
					else
					{
						int v1 = qkth( rt[nst] , add + 1 ) ;
						if ( seg[rt[nst]].sum + query( rt[nst - 1] , v1 + 1 , k - 1 ) >= x ) printf("%lld\n" , ( nv - 1 ) * k 
						+ qkth2( rt[nst] , rt[nst - 1] , x - ( seg[rt[nst]].sum - add ) ) ) ;
						else printf("%lld\n" , a[n - x + 1]) ; 
					}
				}
			}
		}
	}
	return 0 ;
}