N, Q = map(int, input().split())
D = {}
L = []
for q in range(Q):
    query = input().split()
    if query[0] == '1':
        s, r = query[1], int(query[2])
        D[s] = [False, r, s]
        L.append(D[s])
        if (len(L) > N):
            m = min(L)
            print(m[-1])
            L.remove(m)
    elif query[0] == '2':
        x = int(query[1])
        N -= x
        L.sort(reverse=True)
        while len(L) > N:
            m = L.pop()
            print(m[-1])
    elif query[0] == '3':
        s, x = query[1], int(query[2])
        N += x
        D[s][0] = True