import heapq import bisect N, K, Q = map(int, input().split()) A = list(map(int, input().split())) A.sort() ftK = A[: K] atK = A[K:] heapq.heapify(atK) for i in range(Q): query = list(map(int, input().split())) if query[0] == 1: if query[1] >= ftK[-1]: heapq.heappush(atK, query[1]) else: heapq.heappush(atK, ftK.pop()) bisect.insort_left(ftK, query[1]) elif query[0] == 2: slim = ftK.pop() + query[1] if len(atK) >= 1: target = heapq.heappop(atK) if slim <= target: ftK.append(slim) heapq.heappush(atK, target) else: ftK.append(target) heapq.heappush(atK, slim) else: ftK.append(slim) else: print(ftK[-1])