n,K,Q=map(int,input().split()) a=list(map(int,input().split())) from heapq import heappush,heappop a.sort() q1=[-v for v in a[:K][::-1]] q2=a[K:] for _ in range(Q): q=list(map(int,input().split())) t=q[0] if t==1: x=q[1] if -q1[0]<=x: heappush(q2,x) else: heappush(q2,-heappop(q1)) heappush(q1,-x) if t==2: y=q[1] x=-heappop(q1)+y heappush(q2,x) heappush(q1,-heappop(q2)) if t==3: print(-q1[0])