Persistent priority queue

Implement a persistent priority queue.

Input

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

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

• x 0 - Remove the maximum element from the structure identified by number x (0 ≤ 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