import heapq
N,K,Q = map(int,input().split())
A = sorted(list(map(int,input().split())))
heap = A[2:]
B = A[:2]
for _ in range(Q):
    qry = list(map(int,input().split()))
    if len(qry)==1:
        print(heap[0])
    else:
        if qry[0]==3:
            print(heap[0])
        elif qry[0]==1:
            x = qry[1]
            if x>=B[-1]:
                heapq.heappush(heap,x)
            elif x>=B[0]:
                y = B.pop()
                B.append(x)
                heapq.heappush(heap,y)
            else:
                y = B.pop()
                B = [x,B[0]]
                heapq.heappush(heap,y)
        else:
            y = qry[1]
            x = heapq.heappop(heap)
            heapq.heappush(heap,x+y)