K. Colorful Balls - 水以下コンテスト

K - Colorful Balls

Ceylon

1024

100

点

問題文

一方の端が開いていて、もう一方の端が閉じている細長い筒があり、開いているほうが左になるように置かれています。
また、様々な色で塗られたボールがあり、各ボールは $1$ 以上 $10^{9}$ 以下の整数で表される色で塗られています。

はじめ、筒の中は空です。クエリが $Q$ 回与えられるので、順番に処理してください。

各クエリは以下の3種類のいずれかです。

1 x c: 色 $c$ のボールを左から $x$ 個追加する
2 x: 現在の筒の左から $1, 2, \ldots, x$ 番目のボールを取り除く
3 x: 現在の筒の左から $x$ 番目のボールの色を出力する

なお、筒は十分に細く、ボールの順序が入れ替わることはないものとします。

制約

$1 \leq Q \leq 2 \times 10^{5}$
クエリ1に対して、 $1 \leq x \leq 10^{9}$
$1 \leq c \leq 10^{9}$
クエリ2, 3において、その時点で筒の中に $x$ 個以上 ( $x \geq 1$ ) のボールが存在する
入力はすべて整数

部分点

以下の条件を満たすテストケースにすべて正解したとき、記載された点数が与えられます。

(10点) $Q \leq 5000$ , クエリ1, 2に対しては常に $x = 1$
(30点) $Q \leq 5000$
(60点) 追加の制約なし

入力

入力は、以下の形式で標準入力から与えられます。

$Q$
$\mathrm{query}_1$
$\mathrm{query}_2$
$\vdots$
$\mathrm{query}_Q$

各クエリ $\mathrm{query}_i$ は、以下に示す $3$ つの形式のいずれかである。

$1$ $x$ $c$

$2$ $x$

$3$ $x$

出力

クエリ3の個数を $q$ 個として、 $q$ 行出力せよ。
$j (1 \leq j \leq q)$ 行目には、クエリ3のうち $j$ 個目のものに対する答えを出力せよ。

入力例 1

出力例 1

10000
14142

筒の中の状態を左から順番に、数列で表すことにします。
始め、筒の中は $()$ です。

1番目のクエリは1 1 10000です。筒の中の状態は $(10000)$ になります。
2番目のクエリは1 1 14142です。筒の中の状態は $(14142, 10000)$ になります。
3番目のクエリは3 2です。左から $2$ 番目の色である $10000$ を出力します。
4番目のクエリは1 1 17320です。筒の中の状態は $(17320, 14142, 10000)$ になります。
5番目のクエリは2 1です。筒の中の状態は $(14142, 10000)$ になります。
6番目のクエリは3 1です。左から $1$ 番目の色である $14142$ を出力します。

この入力は部分点1の制約を満たします。

入力例 2

出力例 2

2
1

1番目のクエリは1 3 1です。筒の中の状態は $(1, 1, 1)$ になります。
2番目のクエリは1 4 2です。筒の中の状態は $(2, 2, 2, 2, 1, 1, 1)$ になります。
3番目のクエリは1 5 3です。筒の中の状態は $(3, 3, 3, 3, 3, 2, 2, 2, 2, 1, 1, 1)$ になります。
4番目のクエリは3 7です。左から $7$ 番目の色である $2$ を出力します。
5番目のクエリは2 7です。筒の中の状態は $(2, 2, 1, 1, 1)$ になります。
6番目のクエリは3 3です。左から $3$ 番目の色である $1$ を出力します。

この入力は部分点2の制約を満たします。

入力例 3

6
1 1000000000 1
1 1000000000 2
1 1000000000 3
3 2500000000
2 2999999999
3 1

出力例 3

1
1

クエリ2,3において、 $x$ が32bit整数型に収まらないことがあります。

この入力は部分点2の制約を満たします。