Подвійна черга
Нещодавно створена Балканська Інвестиційна Банківська Група (БІГ-Банк) відкрила новий офіс у Бухаресті, обладнаний сучасною обчислювальною технікою від IBM Румунія, з використанням передових інформаційних технологій. У цьому банку кожен клієнт ідентифікується натуральним числом k. Коли клієнт приходить до банку для отримання послуг, йому або їй присвоюється певне натуральне число - пріоритет p. Молоді менеджери банку вирішили змінити традиційний підхід, запропонувавши обслуговувати клієнтів не лише з найбільшим пріоритетом, але й з найменшим. Відомо, що система отримує на вхід такі типи запитів:
0 Зупинити систему обслуговування клієнтів
1 k p Додати клієнта k з пріоритетом p до списку очікування
2 Обслуговувати клієнта з найбільшим пріоритетом і видалити його зі списку очікування
3 Обслуговувати клієнта з найменшим пріоритетом і видалити його зі списку очікування
Вам потрібно допомогти інженеру програмного забезпечення банку, написавши програму, яка обслуговуватиме клієнтів згідно з цими правилами.
Вхідні дані
Кожен вхідний рядок містить один із можливих запитів; лише останній рядок містить запит на зупинку системи (код 0). Якщо надходить запит на додавання клієнта до черги (код 1), вважайте, що на даний момент немає інших запитів для цього клієнта або клієнта з таким же пріоритетом. Значення k завжди менше 10^6, а пріоритет p менше 10^7. Клієнт може приходити і обслуговуватися кілька разів, кожного разу отримуючи різне значення пріоритету.
Вихідні дані
Для кожного запиту з кодом 2 або 3 програма повинна вивести в окремому рядку ідентифікатор обслугованого клієнта. Якщо надходить запит при порожній черзі на обслуговування, слід вивести нуль (0).