当前没有测试数据。

D - 银行

得分：400分

题目描述

有 $N$ 个人排队在银行前面，他们的ID编号分别为 $1,2,\dots,N$。一共会有 $Q$ 个事件，其中有三种类型的事件。

1. 1：出纳员叫号（叫的是那些还没有被叫的最小ID编号的人）。
2. 2 x：ID编号为 $x$ 的人第一次前来办理业务（注意：这个人至少已经被出纳员叫过一次号）。
3. 3：出纳员再次叫号（叫的是那些已经被叫过号但还没有前来的最小ID编号的人）。

请输出在第三类事件中被叫的人的ID编号。

限制条件

• $1 \leq N \leq 5 \times 10^5$
• $2 \leq Q \leq 5 \times 10^5$
• 如果所有人已经至少被叫了一次，就不会再发生第一类事件。
• 对于每个第二类事件，ID编号为 $x$ 的人已经至少被叫了一次。
• 对于每个第二类事件，ID编号为 $x$ 的人不会多次前来。
• 如果所有已经被叫的人都已经前来，就不会再发生第三类事件。
• 至少有一个第三类事件发生。
• 输入中的所有值都是整数。

输入

从标准输入读入的输入格式如下，其中 $\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编号。

样例输入1

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

样例输出1

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、7、10个事件是第三类事件，所以你需要打印出这些事件中集合中最小ID编号的人：1, 2, 4。