import bisect
from collections import defaultdict

n, q = map(int, input().split())
Sr = []  # ソート済みリスト（条件により移動される要素用）
Sn = []  # ソート済みリスト（初期状態の要素用）
D = defaultdict(int)

for _ in range(q):
    A = input().split()
    if A[0] == "1":
        s = A[1]
        r = int(A[2])
        D[s] = r
        # Sn に (r, s) をソート済みリストのまま追加
        bisect.insort(Sn, (r, s))
    elif A[0] == "2":
        x = int(A[1])
        n -= x
    else:  # クエリタイプ "3" と仮定
        s = A[1]
        x = int(A[2])
        n += x
        tup = (D[s], s)
        # Sr に (r, s) をソート済みリストとして追加
        bisect.insort(Sr, tup)
        # Sn から tup を削除
        i = bisect.bisect_left(Sn, tup)
        if i < len(Sn) and Sn[i] == tup:
            Sn.pop(i)
    # Sn と Sr の合計要素数が n を超えている間、最小の要素を取り出す
    while len(Sn) + len(Sr) > n:
        if Sn:
            r, s = Sn.pop(0)
            print(s)
        else:
            r, s = Sr.pop(0)
            print(s)