from sortedcontainers import SortedList

N, K, Q = (int(x) for x in input().split())
A=list(map(int, input().split()))
A=SortedList(A)
ans=[]
for i in range(Q):
    q=list(map(int, input().split()))
    if q[0] == 1:
        A.add(q[1])
    elif q[0] == 2:
        a = A[K-1]
        del A[K-1]
        A.add(a+q[1])
    else:
        ans.append(A[K-1])

for i in ans:
    print(i)