#![allow(unstable_name_collisions)]
use std::collections::BTreeMap;

use proconio::input;

#[derive(Debug)]
struct BTreeMultiSet<T> {
    length: usize,
    counts: BTreeMap<T, usize>,
}
impl<T: Ord + Copy> BTreeMultiSet<T> {
    fn new() -> Self {
        Self { length: 0, counts: BTreeMap::new() }
    }
    fn insert(&mut self, value: T) {
        self.length += 1;
        *self.counts.entry(value).or_default() += 1;
    }
    fn first(&self) -> Option<&T> {
        self.counts.keys().next()
    }
    fn last(&self) -> Option<&T> {
        self.counts.keys().rev().next()
    }
    fn pop_first(&mut self) -> Option<T> {
        let mut count_entry = self.counts.first_entry()?;
        self.length -= 1;
        *count_entry.get_mut() -= 1;
        if *count_entry.get() == 0 {
            Some(count_entry.remove_entry().0)
        } else {
            Some(*count_entry.key())
        }
    }
    fn pop_last(&mut self) -> Option<T> {
        let mut count_entry = self.counts.last_entry()?;
        self.length -= 1;
        *count_entry.get_mut() -= 1;
        if *count_entry.get() == 0 {
            Some(count_entry.remove_entry().0)
        } else {
            Some(*count_entry.key())
        }
    }
}
impl<T: Ord + Copy> From<&[T]> for BTreeMultiSet<T> {
    fn from(value: &[T]) -> Self {
        let mut ret = Self::new();
        for v in value {
            ret.insert(*v);
        }
        ret
    }
}

fn main() {
    input! {
        n: usize, k: usize, q: usize,
        mut a: [i64; n],
    }
    a.sort();

    let mut less = BTreeMultiSet::from(&a[..k]);
    let mut greater = BTreeMultiSet::from(&a[k..]);

    for _ in 0..q {
        input! { query: u8 }
        match query {
            1 => {
                input! { x: i64 }
                less.insert(x);
                greater.insert(less.pop_last().unwrap());
            }
            2 => {
                input! { y: i64 }
                let temp = less.pop_last().unwrap();
                greater.insert(temp + y);
                less.insert(greater.pop_first().unwrap());
            }
            3 => {
                println!("{}", less.last().unwrap());
            }
            _ => {}
        }
    }
}