Persistent priority queue

Input

The first line contains the number of operations, $n$ (1 \le n \le 200000). Each of the following $n$ lines describes an operation $i$:

• $x$ $m$ - Add the number $m$ (0 < m \le 100000) to the structure identified by number $x$ (0 \le x < i).

• $x$ $0$ - Remove the maximum element from the structure identified by number $x$ (0 \le x < i). It is guaranteed that the priority queue $x$ is not empty.

Each operation $i$, described on line i + 1, results in the creation of a new structure numbered $i$. Initially, there is an empty structure numbered zero.

Output

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

Examples