from sortedcontainers import SortedList
N,K,Q=map(int,input().split())
A=SortedList(map(int,input().split()))
for _ in range(Q):
    q=list(map(int,input().split()))
    if q[0]==1:
        A.add(q[1])
    elif q[0]==2:
        s=A.pop(K-1)
        A.add(s+q[1])
    else:
        print(A[K-1])