Persistent Queue

AC一覧

Problem Statement問題文

Let $S_{-1}$ be an empty sequence. Process the following $Q$ queries. The $i$-th query is given in the following form.

• 0 $t_i$ $x_i$: Define $S_i$ as the sequence obtained by adding $x_i$ to the end of $S_{t_i}$.
• 1 $t_i$: Define $S_i$ as the sequence obtained by deleting the front element of $S_{t_i}$. Print the deleted element.

$S_{-1}$ を空の列とします。 $Q$ 個のクエリを処理してください。 $i$ 個目のクエリは以下の形式で与えられます。

• 0 $t_i$ $x_i$: $S_{t_i}$ の末尾に $x_i$ を追加した列を $S_i$ とする。
• 1 $t_i$: $S_{t_i}$ の先頭を削除した列を $S_i$ とする。削除した要素を出力する。

Constraints制約

• $1 \leq Q \leq 500{,}000$
• $-1 \leq t_i < i$
• $0 \leq x_i \leq 10^{9}$
• In query 1, $S_{t_i}$ is not empty.
• $1 \leq Q \leq 500{,}000$
• $-1 \leq t_i < i$
• $0 \leq x_i \leq 10^{9}$
• クエリ 1 について、$S_{t_i}$ は空ではない。

Input入力

$Q$
$\textrm{Query}_0$
$\textrm{Query}_1$
:
$\textrm{Query}_{Q-1}$


Sampleサンプル

# 1

6
0 -1 6
0 0 7
1 0
0 -1 8
1 3
1 1

6
8
6


Timelimit: 5 secs

Before submitting, please confirm terms and conditions