// Not afraid to dark.

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

clock_t start_time, end_time;
#define GET_START start_time = clock ();
#define GET_END end_time = clock (); fprintf (stderr, "TIME COSSEMED : %0.3lf\n", 1.0 * (end_time - start_time) / CLOCKS_PER_SEC);
#define inline __inline__ __attribute__ ((always_inline))

#define int long long

namespace io {
    int read_pos, read_dt; char read_char;
    inline int read (int &p = read_pos){
        p = 0, read_dt = 1; read_char = getchar ();
        while (! isdigit (read_char)){
            if (read_char == '-')
                read_dt = - 1;
            read_char = getchar ();
        }
        while (isdigit (read_char)){
            p = (p << 1) + (p << 3) + read_char - 48;
            read_char = getchar ();
        }
        return p = p * read_dt;
    }
    int write_sta[65], write_top;
    inline void write (int x){
        if (x < 0)
            putchar ('-'), x = - x;
        write_top = 0;
        do
            write_sta[write_top ++] = x % 10, x /= 10;
        while (x);
        while (write_top)
            putchar (write_sta[-- write_top] + 48);
    }
}

const int N = 5e5;
int n, m, k, a[N + 5], rt[N + 5], dv[N + 5], cnt;

namespace Banlanced_Tree{
    int T;
    tree < pair < int , int > , null_type , greater < pair < int , int > > , rb_tree_tag , tree_order_statistics_node_update > tr;
    inline void Clear (){
        T = 0;
        tr.clear ();
    }
    inline void Insert (int x){
        tr.insert (make_pair (x, T ++));
    }
    inline int Kth (int k){
        if (k < 1 || k > T)
            return - 4e18;
        return (*tr.find_by_order (k - 1)).first;
    }
} using namespace Banlanced_Tree;

inline int MOD (int x){
    return (x % k + k) % k;
}
inline int PAR (int x){
    if (x >= 0)
        return x / k;
    else
        return (x - k + 1) / k;
}

signed main (){
    GET_START

    io::read (n), io::read (m), io::read (k);
    for (int i = 1;i <= n;++ i)
        io::read (a[i]);
    sort (a + 1, a + n + 1, [] (const int &x, const int &y){
        return x > y;
    });
    ++ n;
    a[n] = - 4e18;

    for (int i = 1;i <= n;++ i)
        if (i == n || PAR (a[i + 1]) < PAR (a[i])){
            ++ cnt;
            rt[cnt] = i, dv[cnt] = PAR (a[i]);
        }

    int p = 1, rest = 0;
    for (int i = 1;i <= rt[p];++ i)
        Insert (MOD (a[i]));
    
    if (n == 101)
        for (int i = 29;i <= 37;++ i)
            printf ("%lld (%lld)\n", MOD (a[i]), a[i]);

    // int TT = 0;

    while (m --){
        char opt;
        cin >> opt;
        if (opt == 'A'){
            // ++ TT;
            int x = io::read ();
            // if (TT == 23){
                // printf ("%lld %lld [%lld %lld] (%lld %lld) : %lld %lld<<<\n", x, rest, rt[p], rt[p + 1], dv[p], dv[p + 1], Kth (x - (rt[p] - rest)) + (dv[p] - 1) * k, Kth (x + rest) + dv[p] * k);
                // printf ("(%d) > ", (int) tr.size ());
                // for (auto x : tr)
                //     printf ("%lld ", x.first);
                // puts ("");
            // }
            if (x > rt[p])
                io::write (a[x]), puts ("");
            else
            if (x > rt[p] - rest)
                io::write (Kth (x - (rt[p] - rest)) + (dv[p] - 1) * k), puts ("");
            else
                io::write (Kth (x + rest) + dv[p] * k), puts ("");
        } else {
            int t = io::read () + rest;
            while ((dv[p] - dv[p + 1]) * rt[p] <= t){
                t -= (dv[p] - dv[p + 1]) * rt[p];
                for (int i = rt[p] + 1;i <= rt[p + 1];++ i)
                    Insert (MOD (a[i]));
                ++ p;
            }
            dv[p] -= t / rt[p];
            rest = t % rt[p];
        }
    }

    GET_END
    return 0;
}
/*
3 5 5
7 3 9
A 3
C 1
A 2
C 2
A 3
*/
/*
33 33 [37 39] (27 26) : 6103 -3999999999999993709<<<
(37) > 228 218 212 211 197 191 188 177 177 159 151 132 124 123 101 100 90 79 79 77 77 75 74 66 60 57 57 56 45 45 38 37 28 27 16 14 11 

*/