题目描述

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

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

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

输入格式

入力は以下の形式で標準入力から与えられる。ここで $\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$ 番目のもので呼ばれた人の番号を出力せよ。

题目大意

给定数组 $a$ 满足 $a_i=i$ 和空数组 $b$，要求支持 $3$ 种操作：

1. 删除 $a$ 中最小的元素，并将其加入 $b$ 数组。
2. 删除 $b$ 中值为 $x$ 的元素，保证存在。
3. 输出 $b$ 中的最小值。

数组长度为 $n$，有 $m$ 次询问，$n, m\le 5\times 10^5$

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

1
2
4

提示

制約

• $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 回発生する
• 入力される値はすべて整数

Sample Explanation 1

$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$ を出力します。