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