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

import heapq

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

    member_map = {}
    for values in queries:
        if values[0] == "1":
            _, s, r = values
            member_map[s] = r
    member_list= list(member_map.keys())
    member_index_map = {}
    for i, m in enumerate(member_list):
        member_index_map[m] = i

    fixed_members = []
    non_fixed_menbers = []
    fixed_members_set = [False] * len(member_list)
    member_num = 0

    go_homed = []
    for i, values in enumerate(queries):
        if values[0] == "1":
            _, s, r = values
            r = int(r)
            s_index = member_index_map[s]
            heapq.heappush(non_fixed_menbers, (r, s_index))
            member_num += 1
            while member_num > N and len(non_fixed_menbers) > 0:
                r, s_index = heapq.heappop(non_fixed_menbers)
                if not fixed_members_set[s_index]:
                    go_homed.append((i, r, s_index))
                    member_num -= 1
        elif values[0] == "2":
            _, x = values
            N -= int(x)
            while member_num > N and len(non_fixed_menbers) > 0:
                r, s_index = heapq.heappop(non_fixed_menbers)
                if not fixed_members_set[s_index]:
                    go_homed.append((i, r, s_index))
                    member_num -= 1

            while member_num > N:
                r, s_index = heapq.heappop(fixed_members)
                go_homed.append((i, r, s_index))
                member_num -= 1
        elif values[0] == "3":
            _, s, x = values
            s_index = member_index_map[s]
            r = member_map[s]
            x = int(x)
            N += x
            if s not in fixed_members:
                fixed_members_set[s_index] = True
                heapq.heappush(fixed_members, (r, s_index))
    
    go_homed.sort()

    for _, _, s in go_homed:
        print(member_list[s])










if __name__ == "__main__":
    main()