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