D - Hospital Reception Window Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

高橋君は、病院の受付窓口の順番管理システムを担当しています。窓口には 1 つの待ち行列があり、患者は到着順に末尾へ並びます。

しかし、この病院では緊急患者用の優先カードが存在します。優先カードを持っている患者は、待ち行列の指定された位置に割り込むことができます。高橋君は、割り込みが発生するたびに待ち行列全体の状態を正しく把握しておく必要があります。

最初、待ち行列は空です。以下の Q 個の操作が順番に与えられます。

  • 操作 1 : 1 x — 患者番号 x の患者が待ち行列の末尾に並ぶ。
  • 操作 2 : 2 x k — 優先カードを持つ患者番号 x の患者が、待ち行列の先頭から k 番目の位置に挿入される。すなわち、この操作の直後において、待ち行列の先頭から k 番目が患者番号 x の患者となる。挿入前に先頭から k 番目以降にいた患者は、それぞれ 1 つずつ後ろにずれる。
  • 操作 3 : 3 — 待ち行列の先頭の患者が窓口で対応され、待ち行列から取り除かれる。

なお、異なる操作で同じ患者番号が与えられることがありますが、それらは別々の患者として扱われ、それぞれ独立に待ち行列に追加されます。

操作 3 が行われるたびに、取り除かれた患者の患者番号を出力してください。

制約

  • 1 \leq Q \leq 2 \times 10^5
  • 操作 1, 2 における患者番号 x は 1 \leq x \leq 10^9 を満たす整数である。
  • 操作 2 における挿入位置 k は、1 \leq k \leq (\text{その操作の直前の待ち行列の長さ}) + 1 を満たす整数である。特に k がその操作の直前の待ち行列の長さに 1 を加えた値に等しい場合、患者は末尾に追加される。
  • 操作 3 が行われるとき、待ち行列は空でないことが保証される。
  • 入力で与えられる値はすべて整数である。

入力

Q
\text{query}_1
\text{query}_2
\vdots
\text{query}_Q

1 行目には、操作の個数を表す整数 Q が与えられる。

2 行目から Q 行にわたって、各操作が 1 行ずつ与えられる。各行の先頭の整数が操作の種類を表す。

  • 操作 1 の場合: 1 x の形式で、末尾に並ぶ患者の患者番号 x が与えられる。
  • 操作 2 の場合: 2 x k の形式で、割り込む患者の患者番号 x と、挿入先の位置 k が与えられる。
  • 操作 3 の場合: 3 のみが与えられる。

出力

操作 3 が行われるたびに、待ち行列の先頭から取り除かれた患者の患者番号を 1 行に 1 つずつ出力せよ。

入力例 1

7
1 10
1 20
2 30 2
3
2 40 1
3
3

出力例 1

10
40
30

入力例 2

6
2 5 1
1 5
2 7 3
3
3
3

出力例 2

5
5
7

入力例 3

18
1 100
1 200
2 300 1
1 400
2 500 3
3
2 600 5
3
1 700
2 800 2
3
3
2 900 1
1 1000
2 1100 4
3
3
3

出力例 3

300
100
500
800
900
200
400

入力例 4

40
1 1000000000
1 1
1 2
2 999999999 1
2 123456789 3
3
1 3
2 4 6
2 5 2
3
3
1 6
2 7 1
2 8 4
1 9
3
2 10 9
1 11
2 12 5
3
3
2 13 1
2 14 10
1 15
3
1 16
2 17 7
2 18 14
3
3
3
2 19 1
1 20
2 21 13
3
1 22
2 23 15
3
3
3

出力例 4

999999999
1000000000
5
7
123456789
1
13
8
2
12
19
3
4
6

入力例 5

2
2 1000000000 1
3

出力例 5

1000000000

Score : 400 pts

Problem Statement

Takahashi is in charge of the queue management system for a hospital's reception counter. The counter has a single queue, and patients line up at the end in order of arrival.

However, this hospital has priority cards for emergency patients. A patient holding a priority card can cut into the queue at a specified position. Takahashi needs to correctly keep track of the entire state of the queue every time a cut-in occurs.

Initially, the queue is empty. The following Q operations are given in order.

  • Operation 1: 1 x — Patient with patient number x lines up at the end of the queue.
  • Operation 2: 2 x k — A patient with patient number x holding a priority card is inserted at the k-th position from the front of the queue. That is, immediately after this operation, the k-th person from the front of the queue is the patient with patient number x. Patients who were at position k or later from the front before the insertion are each shifted one position back.
  • Operation 3: 3 — The patient at the front of the queue is served at the counter and removed from the queue.

Note that the same patient number may appear in different operations, but they are treated as separate patients and are each independently added to the queue.

Each time operation 3 is performed, output the patient number of the removed patient.

Constraints

  • 1 \leq Q \leq 2 \times 10^5
  • The patient number x in operations 1 and 2 is an integer satisfying 1 \leq x \leq 10^9.
  • The insertion position k in operation 2 is an integer satisfying 1 \leq k \leq (\text{length of the queue immediately before that operation}) + 1. In particular, if k equals the length of the queue immediately before the operation plus 1, the patient is added to the end.
  • When operation 3 is performed, it is guaranteed that the queue is not empty.
  • All values given in the input are integers.

Input

Q
\text{query}_1
\text{query}_2
\vdots
\text{query}_Q

The first line contains an integer Q representing the number of operations.

From the second line onward, each operation is given on a single line over Q lines. The first integer on each line indicates the type of operation.

  • For operation 1: Given in the format 1 x, where x is the patient number of the patient lining up at the end.
  • For operation 2: Given in the format 2 x k, where x is the patient number of the patient cutting in and k is the insertion position.
  • For operation 3: Only 3 is given.

Output

Each time operation 3 is performed, output the patient number of the patient removed from the front of the queue, one per line.

Sample Input 1

7
1 10
1 20
2 30 2
3
2 40 1
3
3

Sample Output 1

10
40
30

Sample Input 2

6
2 5 1
1 5
2 7 3
3
3
3

Sample Output 2

5
5
7

Sample Input 3

18
1 100
1 200
2 300 1
1 400
2 500 3
3
2 600 5
3
1 700
2 800 2
3
3
2 900 1
1 1000
2 1100 4
3
3
3

Sample Output 3

300
100
500
800
900
200
400

Sample Input 4

40
1 1000000000
1 1
1 2
2 999999999 1
2 123456789 3
3
1 3
2 4 6
2 5 2
3
3
1 6
2 7 1
2 8 4
1 9
3
2 10 9
1 11
2 12 5
3
3
2 13 1
2 14 10
1 15
3
1 16
2 17 7
2 18 14
3
3
3
2 19 1
1 20
2 21 13
3
1 22
2 23 15
3
3
3

Sample Output 4

999999999
1000000000
5
7
123456789
1
13
8
2
12
19
3
4
6

Sample Input 5

2
2 1000000000 1
3

Sample Output 5

1000000000