問題文

競プロ部には $100$ 人の部員がおり、競プロ部の部室には $10^9$ 台のパソコンがあります。時刻 $0$ の時点では、そのうち $N$ 台のパソコンが使用可能です。

出来事が $Q$ 個入力されます。$i \ (1 \leq i \leq Q)$ 番目のクエリは、時刻 $i$ に起きた出来事を表します。クエリの入力は、次のような形式で与えられます。

• クエリ1: 1 s r の形式で与えられる。レート $r$ の部員 $s$ が部室に来る。
• クエリ2: 2 x の形式で与えられる。$x$ 個のパソコンが使用不可能になる。
• クエリ3: 3 s x の形式で与えられる。部室にいる部員 $s$ が $x$ 個のパソコンを使用可能にする。

パソコンは、次のような順番で、現在使用可能なパソコンの台数に対し $1$ 人 $1$ 台使います。

• パソコンを $1$ 台でも使用可能にしたことがある人の中でレートが高い順
• 上に当てはまる人全員が使ってもまだ使える台がある場合、上に当てはまらない人の中でレートが高い順

使用可能なパソコンの台数より現在部室にいる部員の人数の方が多くなった場合、上の順番によってパソコンを使える部員を決めて、使えない部員は即座に部室を出て帰ります。

一度帰った人が再度部室に来ることはありません。

帰った人の名前を、帰った時刻が早い人から順に $1$ 人 $1$ 行ずつ全て出力してください。

複数人が同時に帰った場合は、同時に帰った人々の名前をレートが低い人から順に出力してください。

制約

• $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$ は英小文字からなる
• $s$ 以外の入力はすべて整数である
• 部員の名前は高々 $100$ 種類である
• 部員の名前とレートはそれぞれ相異なる
• 使用可能なパソコンの台数は常に $1$ 以上である
• クエリ1で与えられる部員はまだ部室に来ていない
• クエリ3で与えられる部員は部室にいる

入力

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

各クエリは次のように与えられます。

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

出力

帰らなければならなくなった人の名前を問題文で説明した順に $1$ 人 $1$ 行ずつ全て出力してください。

サンプル

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