from sortedcontainers import SortedSet
from collections import defaultdict
n,q=map(int,input().split())
Sr=SortedSet([])
Sn=SortedSet([])
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.add((r,s))
    elif A[0]=="2":
        x=int(A[1])
        n-=x
    else:
        s = A[1]
        x = int(A[2])
        n+=x
        Sr.add((D[s],s))
        Sn.discard((D[s],s))
    while len(Sn)+len(Sr)>n:
        if len(Sn)>0:
            r,s=Sn.pop(0)
            print(s)
        else:
            r, s = Sr.pop(0)
            print(s)