持久队列（Persistent Queue）

问题描述

设 $S_{-1}$ 为空序列。处理 $Q$，第 $i$ 个查询形式如下：

• 0 t_i x_i：定义 $S_i$ 为将 $x_i$ 添加到 $S_{t_i}$ 末尾所得的序列。
• 1 t_i：定义 $S_i$ 为删除 $S_{t_i}$ 首元素所得的序列；输出被删除的元素。

注意：$t_i < i$，且对任意查询 1，$S_{t_i}$ 非空。

约束条件

• $1 \leq Q \leq 5 \times 10^5$
• $-1 \leq t_i < i$
• $0 \leq x_i \leq 10^9$

输入

$Q$
Query₀
Query₁
:
Query$_{Q-1}$

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

6
8
6