import heapq n, k, q = map(int, input().split()) a = list(map(int, input().split())) h1 = [] h2 = [1<<60] for v in a: heapq.heappush(h1, -v) if len(h1) > k: heapq.heappush(h2, -heapq.heappop(h1)) for _ in range(q): query = list(map(int, input().split())) tmp = -heapq.heappop(h1) if query[0] == 1: x = query[1] if tmp > x: heapq.heappush(h1, -x) heapq.heappush(h2, tmp) else: heapq.heappush(h1, -tmp) heapq.heappush(h2, x) elif query[0] == 2: y = query[1] tmp += y tmp2 = heapq.heappop(h2) if tmp2 > tmp: heapq.heappush(h1, -tmp) heapq.heappush(h2, tmp2) else: heapq.heappush(h1, -tmp2) heapq.heappush(h2, tmp) else: print(tmp) heapq.heappush(h1, -tmp)