import heapq N,K,Q = map(int,input().split()) A = list(map(int,input().split())) L = [] R = [] for lp in range(N+Q): if lp < N: query = "1 " + str(A[lp]) else: query = input() if query[0] == "1": _,x = map(int,query.split()) if len(L) < K or -L[0] > x: heapq.heappush(L,-x) else: heapq.heappush(R,x) elif query[0] == "2": _,y = map(int,query.split()) x = -1 * heapq.heappop(L) heapq.heappush(R,x+y) else: print (-1 * L[0]) while len(L) > K: y = -1 * heapq.heappop(L) heapq.heappush(R,y) while len(L) < K and len(R) > 0: y = heapq.heappop(R) heapq.heappush(L,-y)