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.

Examples