eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Подвійна черга

Подвійна черга

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB

Недавно образованная Балканская Инвестиционная Банковская Группа (БИГ-Банк) открыла новый офис в Бухаресте, оснащенный современной вычислительной техникой, предоставленной компанией IBM Румыния, с использованием современных информационных технологий. Как правило, каждый клиент банка идентифицируется натуральным числом k. По приходу в банк за получением услуг, он или она получает некоторое натуральное число - приоритет p. Одно из изобретений молодых менеджеров банка шокировало инженера программного обеспечения по обслуживанию системы. Они решили сломать традицию, предложив обслуживать первым клиента не только с наибольшим приоритетом, но и с наименьшим. Известно, что система на вход получает следующие типы запросов:

0 Система обслуживания клиентов останавливается

1 k p Добавить клиента k с приоритетом p в список ожидания

2 Обслужить клиента с наибольшим приоритетом и удалить из списка ожидания

3 Обслужить клиента с наименьшим приоритетом и удалить из списка ожидания

Вам следует помочь инженеру программного обеспечения банка, написав программу обслуживания клиентов согласно указанному принципу.

Вхідні дані

Каждая входная строка содержит один из возможных запросов; только последняя строка содержит требование остановить работу системы (код 0). Если приходит запрос на включение клиента в очередь (код 1), то считайте, что других запросов по этому клиенту или по клиенту с таким же приоритетом на данный момент не существует. Значение k всегда меньше 10^6, а приоритет p меньше 10^7. Клиент может приходить и обслуживаться несколько раз, каждый раз получая разное значение приоритета.

Вихідні дані

Для каждого запроса с кодом 2 или 3 программа должна вывести в отдельной строке идентификатор обслуженного клиента. Если поступает запрос при пустой очереди на ослуживание, то следует вывести ноль (0).

Приклад

Вхідні дані #1
2
1 20 14
1 30 3
2
1 10 99
3
2
2
0
Вихідні дані #1
0
20
30
10
0
Джерело Southeastern Europe 2007