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

people = []

def delete(people):
    MIN = [4001,-1]
    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:
            people = delete(people)

    elif am[0]=="2":
        N -= int(am[1])
        for i in range(N-num):
            people = delete(people)
        if N > num:
            num = N

    else:
        N += int(am[2])