package main

import . "fmt"
import . "os"
import bf "bufio"
import . "sort"
import "container/heap"

func main() {
	rd:=bf.NewReader(Stdin)
	wr:=bf.NewWriter(Stdout)
	defer wr.Flush()
	
	var n,k,q int
	Fscan(rd,&n,&k,&q)
	a := make([]int, n)
	for i := range a {
		Fscan(rd,&a[i])
	}
	Ints(a)
	
	lb := &PQ{ make([]int,0, n+q), func(x, y int) bool { return x > y } }
	ub := &PQ{ make([]int,0, n+q), func(x, y int) bool { return x < y } }
	
	for i, v := range a {
		if i < k {
			heap.Push(lb, v)
		} else {
			heap.Push(ub, v)
		}
	}
	
	
	for i := 0; i < q; i++ {
		var qc, x, y int
		Fscan(rd, &qc)
		switch qc {
			case 1:
				Fscan(rd,&x)
				if x < lb.Peek() {
					t := heap.Pop(lb)
					heap.Push(lb, x)
					heap.Push(ub, t)
				} else {
					heap.Push(ub, x)
				}
			case 2:
				Fscan(rd,&y)
				e := heap.Pop(lb).(int)
				heap.Push(ub, e+y)
				f := heap.Pop(ub)
				heap.Push(lb, f)
			case 3:
				Fprintln(wr, lb.Peek())
		}
	}
}


type PQ struct {
	buf []int
	less func(x, y int) bool
}

func (pq PQ)Len() int { return len(pq.buf) }
func (pq PQ)Swap(i, j int) { IntSlice(pq.buf).Swap(i, j) }
func (pq PQ)Less(i, j int) bool { return pq.less(pq.buf[i], pq.buf[j]) }
func (pq PQ)Peek() int { return pq.buf[0] }
func (pq *PQ)Push(v any ) {
	pq.buf = append(pq.buf, v.(int))
}
func (pq *PQ)Pop() any {
	old := pq.buf
	n := len(old)
	v := old[n-1]
	pq.buf = old[:n-1]
	return v
}