102943: [Atcoder]ABC294 D - Bank

Problem Statement

$N$ people, with ID numbers $1$, $2$, $\dots$, $N$, are lining up in front of a bank.
There will be $Q$ events. The following three kinds of events can happen.

• 1 : The teller calls the person with the smallest ID number who has not been called.
• 2 x : The person with the ID number $x$ comes to the teller for the first time. (Here, person $x$ has already been called by the teller at least once.)
• 3 : The teller again calls the person with the smallest ID number who has already been called but has not come.

Print the ID numbers of the people called by the teller in events of the third kind.

Constraints

• $1 \leq N \leq 5 \times 10^5$
• $2 \leq Q \leq 5 \times 10^5$
• There will not be an event of the first kind when all people have already been called at least once.
• For each event of the second kind, the person with the ID number $x$ has already been called by the teller at least once.
• For each event of the second kind, the person with the ID number $x$ will not come to the teller more than once.
• There will not be an event of the third kind when all people who have already been called have come to the teller.
• There is at least one event of the third kind.
• All values in the input are integers.

Input

The input is given from Standard Input in the following format, where $\text{event}_i$ denotes the $i$-th event:

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

The description of each event is in one of the following formats:

1

2 $x$

3

Output

Print $X$ lines, where $X$ is the number of events of the third kind.
The $i$-th line should contain the ID number of the person called in the $i$-th event of the third kind.

Sample Input 1

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

Sample Output 1

1
2
4

For each $i = 1, 2, \dots, Q$, shown below is the set of people who have already been called but have not come just before the $i$-th event.

• $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$

The events for $i=3,7,10$ are of the third kind, so you should print the persons with the smallest ID numbers in the sets for those events: $1, 2, 4$.

问题描述

$N$个编号为$1$，$2$，$\dots$，$N$的人在银行前排队。
将会发生$Q$个事件。可以发生的事件有以下三种。

• 1 ：柜员呼叫最小编号未被呼叫的人。
• 2 x ：编号为$x$的人首次来到柜员处。（在这里，编号为$x$的人已经被柜员呼叫至少一次。）
• 3 ：柜员再次呼叫已经呼叫但还未来到的人。

在第三种事件中，柜员呼叫的人的编号。

限制条件

• $1 \leq N \leq 5 \times 10^5$
• $2 \leq Q \leq 5 \times 10^5$
• 当所有人员已经被呼叫至少一次时，不会发生第一种事件。
• 对于第二种事件的每次发生，编号为$x$的人已经被柜员呼叫至少一次。
• 对于第二种事件的每次发生，编号为$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$个呼叫中的人的编号。

样例输入 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$

对于$i=3,7,10$的事件是第三种类型，因此您应该打印在这些事件的集合中具有最小编号的人：$1, 2, 4$。