import heapq n,k,q=list(map(int,input().split())) a=list(map(int,input().split())) a.sort() front=a[:k-1] back=a[k-1:] if k==1: front.append(-1) for i in range(q): f,*x=list(map(int,input().split())) if f==1: if x[0]>=front[-1]: heapq.heappush(back,x[0]) else: y=heapq.heappop(front)*(-1) heapq.heappush(back,y) heapq.heappush(front,x[0]) if f==2: y=heapq.heappop(back) z=x[0]+y heapq.heappush(back,z) if f==3: print(back[0]) # print(front,end="") # print(back)