import heapq n,k,q=list(map(int,input().split())) a=list(map(int,input().split())) heapq.heapify(a) 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())) # print(front) # print(back) if f==1: if x[0]>front[-1]: heapq.heappush(back,x[0]) else: y=front.pop() heapq.heappush(back,y) front.append(x[0]) if f==2: y=heapq.heappop(back) z=x[0]+y if z>front[-1]: heapq.heappush(back,z) else: heapq.heappush(back,front.pop()) front.append(z) if f==3: print(back[0])