Персистентная приоритетная очередь

Реализуйте персистентную приоритетную очередь.

Входные данные

Первая строка содержит количество действий n (1 ≤ n ≤ 200000). Строка номер i + 1 содержит описание действия i:

• x m - добавить в структуру с номером x (0 ≤ x < i) число m (0 < m ≤ 100000);

• x 0 - удалить максимальный элемент со структуры под номером x (0 ≤ x < i). Гарантируется, что приоритетная очередь x не пустая.

В результате действия i, описанной в строке i + 1, образуется новая структура с номером i. Сначала имеется пустой стек с номером ноль.

Выходные данные

Для каждой операции удаления выведите удаляемый элемент в отдельной строке.

Примеры