use std::collections::*;
use std::io::Write;

type Map<K, V> = BTreeMap<K, V>;
type Set<T> = BTreeSet<T>;
type Deque<T> = VecDeque<T>;

fn run() {
    input! {
        n: usize,
        m: usize,
        k: i64,
        a: [i64; n],
        ask: [(String, usize); m],
    }
    let mut a = a;
    a.sort();
    let mut tree = build(&a);
    let out = std::io::stdout();
    let mut out = std::io::BufWriter::new(out.lock());
    for (op, val) in ask {
        if op == "C" {
            let mut rem = val as i64;
            while rem > 0 {
                let max = tree.max().unwrap();
                let (l, mut r) = tree.split_key(max - k + 1);
                let lmax = l.max().unwrap_or(std::i64::MIN / 2);
                let rsize = r.size() as i64;
                let q = (rem / rsize).min((r.min().unwrap() - lmax) / k);
                r.update(q * k);
                rem -= q * k;
                let (a, mut b) = r.split_key(lmax + k);
                if rem >= (b.size() as i64) {
                    rem -= b.size() as i64;
                    b.update(k);
                    tree = l.merge(b).merge(a);
                } else {
                    let s = b.size() - rem as usize;
                    let (c, mut d) = b.split(s);
                    d.update(k);
                    tree = l.merge(d).merge(a).merge(c);
                    rem = 0;
                }
            }
        } else {
            let ans = tree.find_kth(n - val);
            writeln!(out, "{}", ans).ok();
        }
    }
}

fn build(a: &[i64]) -> Tree {
    if a.is_empty() {
        return Tree::default();
    }
    let m = a.len() / 2;
    let v = a[m];
    let mut node = Node {
        val: v,
        max: v,
        min: v,
        sub: 0,
        size: 1,
        left: Tree::default(),
        right: Tree::default(),
    };
    node.left = build(&a[..m]);
    node.right = build(&a[(m + 1)..]);
    node.update();
    Tree(Some(Box::new(node)))
}

fn main() {
    run();
}

#[derive(Default, Debug)]
struct Tree(Option<Box<Node>>);

#[derive(Debug)]
struct Node {
    val: i64,
    max: i64,
    min: i64,
    sub: i64,
    size: usize,
    left: Tree,
    right: Tree,
}

impl Tree {
    fn size(&self) -> usize {
        self.0.as_ref().map_or(0, |p| p.size)
    }
    fn max(&self) -> Option<i64> {
        self.0.as_ref().map(|p| p.max)
    }
    fn min(&self) -> Option<i64> {
        self.0.as_ref().map(|p| p.min)
    }
    fn split(mut self, k: usize) -> (Self, Self) {
        assert!(k <= self.size());
        if k == 0 {
            return (Tree::default(), self);
        }
        if k == self.size() {
            return (self, Tree::default());
        }
        let node = self.0.as_mut().unwrap();
        node.push();
        let l = node.left.size();
        if k <= l {
            let (a, b) = node.take_left().split(k);
            node.left = b;
            node.update();
            (a, self)
        } else {
            let (a, b) = node.take_right().split(k - 1 - l);
            node.right = a;
            node.update();
            (self, b)
        }
    }
    fn split_key(mut self, key: i64) -> (Self, Self) {
        if self.0.is_none() {
            return (Tree::default(), Tree::default());
        }
        let node = self.0.as_mut().unwrap();
        node.push();
        if key <= node.val {
            let (a, b) = node.take_left().split_key(key);
            (a, b.merge(self))
        } else {
            let (a, b) = node.take_right().split_key(key);
            (self.merge(a), b)
        }
    }
    fn merge(mut self, mut rhs: Self) -> Self {
        if self.size() == 0 {
            return rhs;
        }
        if rhs.size() == 0 {
            return self;
        }
        let x = self.size();
        let y = rhs.size();
        if rand() % (x + y) < x {
            let node = self.0.as_mut().unwrap();
            node.push();
            let b = node.take_right().merge(rhs);
            node.right = b;
            node.update();
            self
        } else {
            let node = rhs.0.as_mut().unwrap();
            node.push();
            let b = self.merge(node.take_left());
            node.left = b;
            node.update();
            rhs
        }
    }
    fn update(&mut self, v: i64) {
        self.0.as_mut().map(|node| {
            node.apply(v);
        });
    }
    fn find_kth(&mut self, k: usize) -> i64 {
        assert!(k < self.size());
        let node = self.0.as_mut().unwrap();
        node.push();
        let l = node.left.size();
        if k < l {
            node.left.find_kth(k)
        } else if k == l {
            node.val
        } else {
            node.right.find_kth(k - l - 1)
        }
    }
}

impl Node {
    fn update(&mut self) {
        assert!(self.sub == 0);
        if let Some(v) = self.right.max() {
            self.max = v;
        } else {
            self.max = self.val;
        }
        assert!(self.max >= self.val);
        if let Some(v) = self.left.min() {
            self.min = v;
        } else {
            self.min = self.val;
        }
        assert!(self.min <= self.val);
        self.size = 1 + self.left.size() + self.right.size();
    }
    fn push(&mut self) {
        let sub = self.sub;
        self.sub = 0;
        self.left.update(sub);
        self.right.update(sub);
    }
    fn apply(&mut self, v: i64) {
        self.sub += v;
        self.val -= v;
        self.max -= v;
        self.min -= v;
    }
    fn take_left(&mut self) -> Tree {
        let res = std::mem::take(&mut self.left);
        self.update();
        res
    }
    fn take_right(&mut self) -> Tree {
        let res = std::mem::take(&mut self.right);
        self.update();
        res
    }
}

// ---------- begin input macro ----------
// reference: https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
#[macro_export]
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

#[macro_export]
macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};
    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };
}

#[macro_export]
macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };
    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };
    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };
    ($iter:expr, bytes) => {
        read_value!($iter, String).bytes().collect::<Vec<u8>>()
    };
    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };
    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}
// ---------- end input macro ----------
fn rand_memory() -> usize {
    Box::into_raw(Box::new("I hope this is a random number")) as usize
}

fn rand() -> usize {
    static mut X: usize = 0;
    unsafe {
        if X == 0 {
            X = rand_memory();
        }
        X ^= X << 13;
        X ^= X >> 17;
        X ^= X << 5;
        X
    }
}

fn shuffle<T>(a: &mut [T]) {
    for i in 1..a.len() {
        let p = rand() % (i + 1);
        a.swap(i, p);
    }
}