Персистентна пріоритетна черга

Реалізуйте персистентну пріоритетну чергу.

Вхідні дані

Перший рядок містить кількість дій 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. Спочатку є порожній стек з номером нуль.

Вихідні дані

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

Приклади