とある森には $N$ 羽の鳥が住んでおり、個体識別のために $1, 2, \dots, N$ の番号が順に付けられています。

Alice はこの森にバードウォッチングをしにきました。バードウォッチングをする観測地点にははじめ鳥は存在しませんでした。

Alice がバードウォッチングを開始してから終了するまでの間に、 $M$ 個の出来事が順番に起こりました。 $i$ 番目の出来事は、整数 $t_i, x_i$ を用いて次のように表されます。

• $t_i = 1$ のとき、番号 $x_i$ の鳥が観測地点にやってきたことを表す。
• $t_i = 2$ のとき、番号 $x_i$ の鳥が観測地点から去ったことを表す。
• $t_i = 3$ のとき、Alice がこの出来事が起こった時点で観測地点にいるすべての鳥が写るように写真を $1$ 枚撮ったことを表す。

Alice がバードウォッチングを終了するまでに撮ることができた鳥の番号を昇順にすべて出力してください。ただし、番号 $i$ の鳥を撮ることができたとは、Alice が撮った写真のうち番号 $i$ の鳥が写っている写真が $1$ 枚以上存在することを表します。

Hard (25点)

• $1 \le N \le 10^9$
• $1 \le M \le 3 \times 10^5$
• $t_i \in \lbrace 1, 2, 3 \rbrace$
• $t_i = 1, 2$ のとき、 $1 \le x_i \le N$
• $t_i = 3$ のとき、 $x_i = 0$
• $t_i = 1$ のとき、 $x_i$ 番の鳥はその時点で観測地点に来ていない
• $t_i = 2$ のとき、 $x_i$ 番の鳥はその時点で観測地点に来ている
• 入力はすべて整数

Normal (25点)

• Hardの制約に以下の制約を追加
• $1 \le N \le 3 \times 10^5$

Easy (50点)

• Hardの制約に以下の制約を追加
• $1 \le N \le 3000$
• $1 \le M \le 3000$

入力は以下の形式で標準入力から与えられる。

写真を撮ることができた鳥の個体数を $K$ として、 $K$ 行出力せよ。

$i$ 行目には、写真を撮ることができた鳥の番号を昇順に並べ替えたときの、 $i$ 番目の番号を出力せよ。