import heapq n, k, q = map(int, input().split()) a = list(map(int, input().split())) heapq.heapify(a) for _ in range(q): query = list(map(int, input().split())) if query[0] == 1: heapq.heappush(a, query[1]) elif query[0] == 2: smallest_k = heapq.nsmallest(k, a) if len(smallest_k) < k: continue target = smallest_k[-1] a.remove(target) heapq.heapify(a) heapq.heappush(a, target + query[1]) else: smallest_k = heapq.nsmallest(k, a) if len(smallest_k) < k: print(-1) else: print(smallest_k[-1])