Problem Statement

The competitive programming club has $100$ members, and the club room has $10^9$ computers. At time $0$, $N$ of those computers are usable.

$Q$ events are given as input. The $i \ (1 \leq i \leq Q)$-th query represents the event that occurred at time $i$. The queries are given in the following formats.

• Query 1: Given in the format 1 s r. Member $s$ with rating $r$ comes to the club room.
• Query 2: Given in the format 2 x. $x$ computers become unusable.
• Query 3: Given in the format 3 s x. Member $s$, who is in the club room, makes $x$ computers usable.

Out of the currently usable computers, members use computers at $1$ computer per $1$ person, in the following order.

• First, those who have ever made at least $1$ computer usable, in descending order of rating.
• If computers are still available after everyone above has taken one, those who do not fall under the above, in descending order of rating.

If the number of members currently in the club room exceeds the number of usable computers, the members who can use a computer are determined by the order above, and those who cannot immediately leave the club room and go home.

A person who has gone home never comes to the club room again.

Print the names of all people who went home, in order of the time they went home from earliest to latest, with $1$ person per $1$ line.

If multiple people go home at the same time, print their names in ascending order of rating.

Constraints

• $1 \leq N \leq 100$
• $1 \leq Q \leq 100000$
• $0 \leq r \leq 4000$
• $1 \leq x \leq 10$
• $1 \leq |s| \leq 100$
• $s$ consists of lowercase English letters
• All inputs other than $s$ are integers
• There are at most $100$ distinct member names
• Member names are pairwise distinct, and ratings are pairwise distinct
• The number of usable computers is always at least $1$
• The member given in Query 1 has not yet come to the club room
• The member given in Query 3 is in the club room

Input

$N\ Q$
$\text{query}_1$
$\text{query}_2$
$\vdots$
$\text{query}_Q$

Each query is given as follows.

1 $s$ $r$
2 $x$
3 $s$ $x$

Output

Print the names of all people who had to go home, in the order described in the problem statement, with $1$ person per $1$ line.

Sample

1 5
1 fact 2400
3 fact 2
1 kyoproking 3900
1 yoyoyo 1700
1 pura 1100

pura

10 3
1 yakisobatabetai 0
2 9
1 yakisobairanai 1

yakisobatabetai

3 11
1 magentor 2000
1 warabi 1650
1 kinugoshi 1400
3 kinugoshi 1
2 3
3 kinugoshi 1
1 zeta 2300
3 zeta 2
1 highlightermath 1700
2 2
1 kyoproking 3900

warabi
magentor
highlightermath
kyoproking