银行

题目描述

ID 号为 $1, 2, \dots, N$ 的 $N$ 个人正在银行门口排队。

接下来会发生 $Q$ 个事件。事件有以下三种类型。

1：柜台叫号，叫到编号最小的且尚未被叫过的人。

2 x：ID 号为 $x$ 的人第一次来到柜台。（这里，人 $x$ 已经被叫过至少一次。）

3：柜台再次叫号，叫到已经叫过但还没来柜台的人中编号最小的。

请输出所有第三种事件中被叫到的人的 ID 号。

输入格式

输入按以下格式从标准输入给出，其中 $\text{event}_i$ 表示第 $i$ 个事件：

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

每个事件的描述为以下三种格式之一：

1

2 $x$

3

输出格式

输出 $X$ 行，其中 $X$ 是第三种事件的个数。

第 $i$ 行输出在第 $i$ 个第三种事件中被叫到的人的 ID 号。

样例

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$

第 $i=3,7,10$ 个事件是第三种事件，因此分别输出这些集合中编号最小的人：$1, 2, 4$。

数据范围

• $1 \le N \le 5 \times 10^5$
• $2 \le Q \le 5 \times 10^5$
• 当所有人都已经被叫过至少一次时，不会出现第一种事件
• 对于每个第二种事件，ID 号为 $x$ 的人已经被叫过至少一次
• 对于每个第二种事件，ID 号为 $x$ 的人不会来柜台超过一次
• 当所有被叫过的人都已经来过柜台时，不会出现第三种事件
• 至少有一个第三种事件
• 输入中的所有值均为整数