from sortedcontainers import SortedList def solve(): n,k,q = map(int, input().split()) a = list(map(int, input().split())) s = SortedList(a) for _ in range(q): query = list(map(int, input().split())) if query[0] == 1: s.add(query[1]) elif query[0] == 2: s.add(s.pop(k-1) + query[1]) else: # print("ans" + str(s[k-1])) print(s[k-1]) if __name__ == "__main__": solve()