配点 : $400$ 点

問題文

銀行に人 $1$, 人 $2$, $\dots$, 人 $N$ が並んでいます。 $Q$ 個のイベントが発生します。イベントは次の $3$ 種類のいずれかです。

• 1 : 受付に呼ばれていない人のうち、最も小さい番号の人が受付に呼ばれる。
• 2 x : 人 $x$ が初めて受付に行く。(ここで、人 $x$ はすでに 1 回以上受付に呼ばれている。)
• 3 : すでに受付に呼ばれているが受付に行っていない人のうち、最も小さい番号の人が再度呼ばれる。

$3$ 種類目のイベントで受付に呼ばれる人の番号を呼ばれた順に出力してください。

制約

• $1 \leq N \leq 5 \times 10^5$
• $2 \leq Q \leq 5 \times 10^5$
• 全ての人が 1 回以上呼ばれているときに $1$ 種類目のイベントが発生することはない
• $2$ 種類目のイベントについて、人 $x$ はすでに 1 回以上受付に呼ばれている
• $2$ 種類目のイベントについて、人 $x$ が 2 回以上受付に行くことはない
• 呼ばれている人が全員すでに受付に行っているときに $3$ 種類目のイベントが発生することはない
• $3$ 種類目のイベントは少なくとも 1 回発生する
• 入力される値はすべて整数

入力

入力は以下の形式で標準入力から与えられる。ここで $\text{event}_i$ は $i$ 番目のイベントを意味する。

$N$ $Q$

$\text{event}_1$

$\text{event}_2$

$\vdots$

$\text{event}_Q$

イベントは次の 3 つのいずれかの形式で入力される。

1

2 $x$

3

出力

入力で与えられる $3$ 種類目のイベントの個数を $X$ として、$X$ 行出力せよ。 $i$ 行目には、$3$ 種類目のイベントのうち $i$ 番目のもので呼ばれた人の番号を出力せよ。

4 10
1
1
3
2 1
1
2 3
3
1
2 2
3

1
2
4

$i = 1, 2, \dots, Q$ について、$i$ 番目のイベントが起こる前の時点での、受付に呼ばれたが受付に行っていない人の集合を列挙すると次のようになります。

• $i=1$ : $\lbrace \rbrace$
• $i=2$ : $\lbrace 1\rbrace$
• $i=3$ : $\lbrace 1,2\rbrace$
• $i=4$ : $\lbrace 1,2\rbrace$
• $i=5$ : $\lbrace 2\rbrace$
• $i=6$ : $\lbrace 2,3\rbrace$
• $i=7$ : $\lbrace 2\rbrace$
• $i=8$ : $\lbrace 2\rbrace$
• $i=9$ : $\lbrace 2,4\rbrace$
• $i=10$ : $\lbrace 4\rbrace$

$3$ 種類目のイベントは $i=3,7,10$ のときに発生しているので、その時点での集合のうち番号が最小の人である $1, 2, 4$ を出力します。