import heapq N,K,Q = map(int,input().split()) A = list(map(int,input().split())) A.sort() pos = A[K-1] B = [] C = [] for i in range(K-1): B.append(-A[i]) for i in range(K-1,N): C.append(A[i]) heapq.heapify(B) heapq.heapify(C) for z in range(Q): q = list(map(int,input().split())) if q[0] == 1: x = q[1] if x >= pos: heapq.heappush(C,x) else: heapq.heappush(B,-x) t = heapq.heappop(B) heapq.heappush(C,-t) elif q[0] == 2: y = q[1] t = heapq.heappop(C) heapq.heappush(C,t+y) else: print(pos) pos = heapq.heappop(C) heapq.heappush(C,pos)