Persistent Queue

Problem Statement

問題文

$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 \le Q \le 500{,}000$
• $-1 \le t_i \lt i$
• $0 \le x_i \le 10^{9}$
• クエリ 1 について、$S_{t_i}$ は空ではない

Input

入力

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

# 1

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

6
8
6

Forum