8852: [yosupo] Data Structure - Persistent Queue
[Creator : ]
Description
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.
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.
Input
$Q$
$\textrm{Query}_0$
$\textrm{Query}_1$
:
$\textrm{Query}_{Q-1}$
$\textrm{Query}_0$
$\textrm{Query}_1$
:
$\textrm{Query}_{Q-1}$
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 t_i < i$
- $0 \leq x_i \leq 10^9$
- In query 1, $S_{t_i}$ is not empty.
Sample 1 Input
6
0 -1 6
0 0 7
1 0
0 -1 8
1 3
1 1
Sample 1 Output
6
8
6