import heapq
N,Q = map(int,input().split())
tot = N
cnt = N
que = []
ast = set()
for _ in range(Q):
    qry = list(input().split())
    if qry[0]=="1":
        s,r = qry[1:]
        r = int(r)
        heapq.heappush(que,(r,s))
        if cnt>0:
            cnt -= 1
        else:
            while True:
                r0,s0 = heapq.heappop(que)
                if s0 not in ast:
                    print(s0)
                    break
                else:
                    if r0>=10000:
                        ast.discard(s0)
                        print(s0)
                        break
                    else:
                        r0 += 10000
                        heapq.heappush(que,(r0,s0))
    elif qry[0]=="2":
        x = int(qry[1])
        if cnt>=x:
            cnt -= x
            tot -= x
        else:
            d = x-cnt
            tot -= cnt
            cnt = 0
            outs = []
            while d>0:
                r,s = heapq.heappop(que)
                if s not in ast:
                    tot -= 1
                    d -= 1
                    heapq.heappush(outs,(r,s))
                else:
                    if r>=10000:
                        r -= 10000
                        tot -= 1
                        ast.discard(s)
                        d -= 1
                        heapq.heappush(outs,(r,s))
                    else:
                        r += 10000
                        heapq.heappush(que,(r,s))
            while outs:
                r,s = heapq.heappop(outs)
                print(s)
    else:
        s,x = qry[1:]
        x = int(x)
        ast.add(s)
        tot += x
        cnt += x