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:] 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: heapq.heappush(back,front.pop()) front.append(x[0]) if f==2: y=heapq.heappop(back) x=x[0]+y if x>front[-1]: heapq.heappush(back,x) else: heapq.heappush(back,front.pop()) front.append(x) if f==3: print(back[0])