// 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){
        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] = - 4000000000000000000;

    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]);
        }
    printf ("%lld %lld %lld\n", cnt, rt[cnt], dv[cnt]);

    int p = 1, rest = 0;
    for (int i = 1;i <= rt[p];++ i)
        Insert (MOD (a[i]));

    int TT = 0;

    while (m --){
        char opt;
        cin >> opt;
        if (opt == 'A'){
            ++ TT;
            if (TT == 23)
                printf ("%lld<<<\n", opt);
            int x = io::read ();
            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
*/