可持久化队列

【题目描述】

设 $S_{-1}$ 为空序列。依次处理以下 $Q$ 个查询。 第 $i$ 个查询给出形式如下。

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

【输入】

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

【输出】

对每个 1 $t_i$ 查询，输出一行一个整数，表示被删除的元素。

【输入样例】

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

【输出样例】

6
8
6

【数据范围】

• $1 \leq Q \leq 500000$
• $-1 \leq t_i < i$
• $0 \leq x_i \leq 1000000000$
• 对于查询 1，$S_{t_i}$ 非空。

【来源】

Library Checker（yosupo06） persistent_queue