## https://yukicoder.me/problems/no/3298

import heapq

def main():
    K, K, Q = map(int, input().split())
    A = list(map(int, input().split()))

    queries = []
    for _ in range(Q):
        values = tuple(map(int, input().split()))
        queries.append(values)

    
    lower_queue = []
    upper_queue = []

    for a in A:
        if len(lower_queue) < K:
            heapq.heappush(lower_queue, -a)
        else:
            if -lower_queue[-1] > a:
                old_a = heapq.heappop(lower_queue)
                old_a = -old_a
                heapq.heappush(lower_queue, -a)
                heapq.heappush(upper_queue, old_a)
            else:
                heapq.heappush(upper_queue, a)

    for values in queries:
        if values[0] == 1:
            _, a = values
            if -lower_queue[0] > a:
                old_a = heapq.heappop(lower_queue)
                old_a = -old_a
                heapq.heappush(lower_queue, -a)
                heapq.heappush(upper_queue, old_a)
            else:
                heapq.heappush(upper_queue, a)
        elif values[0] == 2:
            _, y = values
            a = heapq.heappop(lower_queue)
            a = -a
            b = a + y
            if len(upper_queue) == 0 or upper_queue[0] >= b:
                heapq.heappush(lower_queue, -b)
            else:
                x = heapq.heappop(upper_queue)
                heapq.heappush(lower_queue, -x)
                heapq.heappush(upper_queue, b)
        else:
            print(-lower_queue[0])













                




if __name__ == "__main__":
    main()