Problems
Persistent stack
Persistent stack
Implement the persistent stack.
Input
The first line contains the number of operations n (1 ≤ n ≤ 200000). The line i + 1 describes the operation i:
- t m - add to the stack number t (0 ≤ t < i) the number (0 < m ≤ 1000);
- t 0 - delete the last element from the stack number t (0 ≤ t < i). It is guaranteed that the stack t is not empty.
The result of operation i, given in the line i + 1, the stack number i is created. Initially you have an empty stack with number zero.
All input numbers are integers.
Output
For each delete operation print the deleted element in a separate line.
Input example #1
8 0 1 1 5 2 4 3 2 4 3 5 0 6 6 1 0
Output example #1
3 1