// 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;

multiset < int > st;

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]), st.insert (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 = 1;i <= 37;++ i)
        //     printf ("%lld %lld (%lld %lld)\n", MOD (a[i]), PAR (a[i]), MOD (a[i]) + PAR (a[i]) * k, a[i]);

    int TT = 0, all = 0;


    while (m --){
        char opt;
        cin >> opt;
        if (opt == 'A'){
            ++ TT;
            int x;
            cin >> x;
            // int x = io::read ();
            if (TT == 23){
                io::write (x), puts ("");
                // int u = 0;
                // for (int i = 1;i <= rt[p];++ i)
                //     u += PAR (a[i]) - dv[p];
                // printf ("%lld [%lld %lld %lld] (%lld %lld) : %lld %lld<<<\n", x, rest, u, all, 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 ("");
                // printf ("(%d) > ", (int) st.size ());
                // for (auto x : st)
                //     printf ("%lld ", x);
                // 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;
            cin >> t;
            // if (n == 101 && TT < 23)
            //     printf ("C %lld\n", t);
            for (int tt = 1;tt <= t;++ tt){
                int e = *st.rbegin ();
                st.erase (st.find (e));
                e -= k;
                st.insert (e);
            }
            all += t;
            t += 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 

37 20 233
9876
9861
9421
9377
9161
9153
8977
8721
8637
8465
8433
8415
8119
8113
8081
8054
8001
8001
7901
7840
7745
7633
7513
7501
7451
7441
7251
7201
7001
6945
6881
6817
6701
6601
6561
6329
6305 
C 11
C 1
C 39
C 29
C 15
C 1
C 8
C 1
C 4
C 1
C 33
C 1
C 25
C 1
C 19
C 25
C 5
C 17
C 37
A 33

*/