N,K,Q=map(int,input().split())
A=list(map(int,input().split()))
from heapq import heappush,heappop
S0=[]
S1=[]
A.sort()
for i in range(K):
  x=A[i]
  heappush(S0,-x)
for i in range(K,N):
  x=A[i]
  heappush(S1,x)
heappush(S1,10**18)
for _ in range(Q):
  t,*B=map(int,input().split())
  if t==1:
    y=B[0]
    x=heappop(S0)
    x=-x
    if y>x:
      heappush(S1,y)
      heappush(S0,-x)
    else:
      heappush(S1,x)
      heappush(S0,-y)
  elif t==2:
    k=B[0]
    x=heappop(S0)
    x=-x
    x+=k
    y=heappop(S1)
    if x>y:
      heappush(S1,x)
      heappush(S0,-y)
    else:
      heappush(S0,-x)
      heappush(S1,y)
  else:
    result=heappop(S0)
    print(-result)
    heappush(S0,result)