use std::{cmp::Reverse, collections::BinaryHeap};

use proconio::input;

fn solve() -> Vec<u64> {
  input! {
    n: usize,
    k: usize,
    q: usize,
    a: [u64; n],
  }
  let mut queue = KthLargest::new(k);
  for &ai in a.iter() {
    queue.push(ai);
  }
  let mut ans = Vec::new();
  for _ in 0..q {
    input! {
      t: u8,
    }
    match t {
      1 => {
        input! {
          x: u64,
        }
        queue.push(x);
      },
      2 => {
        input! {
          y: u64,
        }
        let s = queue.pop_kth();
        queue.push(s + y);
      },
      3 => {
        ans.push(queue.kth());
      },
      _ => unreachable!(),
    }
  }
  ans
}

fn main() {
  let ans = solve();
  eprintln!("{:?}", ans);
  for x in ans {
    println!("{}", x);
  }
}

struct KthLargest {
  k: usize,
  heap0: BinaryHeap<u64>,
  heap1: BinaryHeap<Reverse<u64>>,
}

impl KthLargest {
  fn new(k: usize) -> Self {
    Self {
      k,
      heap0: BinaryHeap::new(),
      heap1: BinaryHeap::new(),
    }
  }

  fn push(&mut self, x: u64) {
    self.heap0.push(x);
    if self.heap0.len() >= self.k {
      let v = self.heap0.pop().unwrap();
      self.heap1.push(Reverse(v));
    }
  }

  fn pop_kth(&mut self) -> u64 {
    self.heap1.pop().unwrap().0
  }

  fn kth(&self) -> u64 {
    self.heap1.peek().unwrap().0
  }
}