#include<bits/stdc++.h>
using namespace std ;
typedef long long ll ;
typedef unsigned long long ull ;
typedef pair < int , int > pii ;
typedef vector < int > vi ;
#define fi first
#define se second
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()

const int MAXN = 5e5 + 7 ;

int n , q ;
ll k ;
ll a[ MAXN ] ;
ll coef[ MAXN ] ;
pair < ll , int > srt[ MAXN ] ;
int rem_ord[ MAXN ] ;

ll high_coef ;
ll cnt_in_cycle ;
int id_next_high ;
int tp ;

class Tree {
public :
    int tr[ 4 * MAXN ] ;
    void init ( int w , int l , int r ) {
        tr[ w ] = 0 ;
        if ( l == r ) { return ; }
        int mid = ( l + r ) / 2 ;
        init ( 2 * w , l , mid ) ;
        init ( 2 * w + 1 , mid + 1 , r ) ;
    }
    void update ( int w , int l , int r , int pos ) {
        ++ tr[ w ] ;
        if ( l == r ) { return ; }
        int mid = ( l + r ) / 2 ;
        if ( pos <= mid ) { update ( 2 * w , l , mid , pos ) ; }
        else { update ( 2 * w + 1 , mid + 1 , r , pos ) ; }
    }
    int query ( int w , int l , int r , int pos ) {
        if ( l == r ) { return srt[ l ].fi ; }
        int mid = ( l + r ) / 2 ;
        if ( tr[ 2 * w + 1 ] >= pos ) { return query ( 2 * w + 1 , mid + 1 , r , pos ) ; }
        else { return query ( 2 * w , l , mid , pos - tr[ 2 * w + 1 ] ) ; }
    }
};

Tree w ;

void solve ( ) {
    cin >> n >> q >> k ;
    for ( int i = 1 ; i <= n ; ++ i ) {
        cin >> a[ i ] ;
    }
    sort ( a + 1 , a + n + 1 ) ;
    for ( int i = 1 ; i <= n ; ++ i ) {
        coef[ i ] = a[ i ] / k ;
        srt[ i ] = { a[ i ] % k , i } ;
    }
    sort ( srt + 1 , srt + n + 1 ) ;
    for ( int i = 1 ; i <= n ; ++ i ) {
        rem_ord[ srt[ i ].se ] = i ;
    }
    tp = n + 1 ;
    high_coef = coef[ n ] ;
    id_next_high = 0 ;
    while ( tp > 1 && coef[ tp - 1 ] == high_coef ) {
        -- tp ;
        ++ cnt_in_cycle ;
        w.update ( 1 , 1 , n , rem_ord[ tp ] ) ;
    }
    while ( q -- ) {
        char type ;
        cin >> type ;
        if ( type == 'C' ) {
            ll cnt ; cin >> cnt ;
            while ( cnt > 0 ) {
                __int128 mxops ;
                if ( cnt_in_cycle == n ) { mxops = cnt + 1 ; }
                else { 
                    mxops = ( high_coef - coef[ tp - 1 ] ) ;
                    mxops *= cnt_in_cycle ;
                    mxops -= id_next_high ;
                }
                if ( mxops >= cnt ) {
                    high_coef -= ( cnt / cnt_in_cycle ) ;
                    cnt %= cnt_in_cycle ;
                    if ( cnt + id_next_high >= cnt_in_cycle ) {
                        -- high_coef ;
                    }
                    id_next_high = ( id_next_high + cnt ) % cnt_in_cycle ;
                    break ;
                }
                else {
                    cnt -= mxops ;
                    high_coef = coef[ tp - 1 ] ;
                    id_next_high = 0 ;
                    while ( tp > 1 && coef[ tp - 1 ] == high_coef ) {
                        -- tp ;
                        ++ cnt_in_cycle ;
                        w.update ( 1 , 1 , n , rem_ord[ tp ] ) ;
                    }
                }
            }
        }
        else {
            int pos ; cin >> pos ;
            if ( pos > cnt_in_cycle ) {
                cout << a[ n - pos + 1 ] << "\n" ;
            }
            else {
                if ( id_next_high + pos <= cnt_in_cycle ) {
                    ll rem = w.query ( 1 , 1 , n , id_next_high + pos ) ;
                    cout << high_coef * k + rem << "\n" ;
                }
                else {
                    ll rem = w.query ( 1 , 1 , n , ( id_next_high + pos - 1 ) % cnt_in_cycle + 1 ) ;
                    cout << ( high_coef - 1 ) * k + rem << "\n" ;
                }
            }
        }
    }
}

int main ( ) {
    ios_base :: sync_with_stdio ( false ) ;
    cin.tie ( NULL ) ;
    int t = 1 ; // cin >> t ;
    while ( t -- ) { solve ( ) ; }
    return 0 ;
}