D - Bank 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 400 点

問題文

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

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

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

制約

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

入力

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

入力例 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 種類目のイベントは i=3,7,10 のときに発生しているので、その時点での集合のうち番号が最小の人である 1, 2, 4 を出力します。

Score : 400 points

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.