N,Q = map(int,input().split())
num = 0

people = []
solve = []

def delete(people):
    MIN = [10**5,0]
    for i in range(len(people)):
        if people[i][1] < MIN[0]:
            MIN = [people[i][1],i]
    print(people.pop(MIN[1])[0])
    return people

for i in range(Q):
    am = input().split()
    if am[0] == "1":
        people.append([am[1],int(am[2])])
        num += 1
        if num > N:
            if len(people) > 0:
                people = delete(people)
            else:
                solve = delete(solve)

    elif am[0]=="2":
        N -= int(am[1])
        temp = 0
        for i in range(num-N):
            if len(people) > 0:
                people = delete(people)
            elif len(solve) > 0:
                solve = delete(solve)
            else:
                temp += 1
        if N < num:
            num = N + temp
    else:
        N += int(am[2])
        i = 0
        while i < len(people):
            if people[i][0]==am[1]:
                solve.append(people.pop(i))
                i -= 1
            i += 1