Искусство алхимии
(Время: 1 сек. Память: 16 Мб Сложность: 35%)
Толян – известный в узких кругах алхимик. Он держит алхимическую лабораторию и продаёт зелья влиятельным персонам. Цена зелья определяется абсолютной величиной разности магического заряда зелья и специального параметра W, который равен магическому заряду обыкновенной воды.
Жизненный цикл лаборатории состоит из событий следующего типа:
- Приходит тайный покупатель, которому Толян продаёт одну порцию самого дорогого зелья из имеющихся в наличии; если зелья закончились, то покупатель вздыхает и уходит.
- Толян создаёт k порций зелья магического заряда m.
Изначально у Толи нет ни одного зелья. По заданной цепочке событий выведите для каждого покупателя стоимость купленного им зелья. Если к моменту прихода покупателя ни одного зелья в наличии не оказалось, выведите –1.
Входные данные
В первой строке входного файла INPUT.TXT содержатся два целых числа n и W (0 ≤ n ≤ 2×105; 1 ≤ W ≤ 105).
Далее следует n строк, описывающих последовательные события:
- если строка содержит одно число 1, то пришёл покупатель;
- если строка начинается с 2, то Толян создал новые порции зелья. Тогда в той же строке далее заданы ещё два целых числа k и m (1 ≤ k ≤ 1000; 1 ≤ m ≤ 105) – количество порций зелья и магический заряд каждого из них.
Выходные данные
Для каждого события первого типа в порядке их следования во входных данных в выходной файл OUTPUT.TXT выведите одно
целое число – значение магического заряда зелья, которое купил очередной покупатель. Если существует несколько вариантов выбора зелья с максимальной стоимостью, выведите наибольшее из возможных значений. Если к моменту прихода покупателя у Толяна не было ни одного зелья, выведите –1.
Примеры
№ | INPUT.TXT | OUTPUT.TXT |
1 | 9 10
2 1 12
2 2 3
1
2 2 4
2 1 43
1
2 1 100
1
1 | 3
43
100
3 |
2 | 4 10
1
1
2 1 10
1 | -1
-1
10 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
|