Persistent Queue

Input

The first line contains the number of operations $n$ (1 \leq n \leq 200000). The (i+1)-th line contains the description of the $i$-th operation:

• $1tm$ — add the number $m$ to the end of queue number $t$ (0 \leq t < i);

• $-1t$ — remove the first element from queue number $t$ (0 \leq t < i).

As a result of the $i$-th operation, described in the (i+1)-th line, a new queue numbered $i$ is created. Initially, there is an empty queue numbered zero.

All numbers in the input are $32$-bit signed integers.

Output

For each remove operation, output the removed element on a separate line.

Examples