Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Курсы ККДП
Дистрибутивы
Статьи
Ссылки


 

Искусство алхимии

(Время: 1 сек. Память: 16 Мб Сложность: 35%)

Толян – известный в узких кругах алхимик. Он держит алхимическую лабораторию и продаёт зелья влиятельным персонам. Цена зелья определяется абсолютной величиной разности магического заряда зелья и специального параметра W, который равен магическому заряду обыкновенной воды.

Жизненный цикл лаборатории состоит из событий следующего типа:

  1. Приходит тайный покупатель, которому Толян продаёт одну порцию самого дорогого зелья из имеющихся в наличии; если зелья закончились, то покупатель вздыхает и уходит.
  2. Толян создаёт 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.TXTOUTPUT.TXT
19 10
2 1 12
2 2 3
1
2 2 4
2 1 43
1
2 1 100
1
1
3
43
100
3
24 10
1
1
2 1 10
1
-1
-1
10

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!


 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 Тренировочные олимпиады
 Личные олимпиады
 Командные олимпиады
 Первая командная олимпиада
 Вторая командная олимпиада
 Третья командная олимпиада
 Четвертая командная олимпиада
 Пятая командная олимпиада
 Шестая командная олимпиада
 Седьмая командная олимпиада
 A. Сезонное весеннее обострение
 B. Возрастающий массив
 C. Волшебный прямоугольник
 D. Эффект домино
 E. Независимое множество
 F. Искусство алхимии
 G. Робот
 H. Кроссворд

Красноярский краевой Дворец пионеров, (c)2006 - 2024, ИНН 246305493507, E-mail: admin@acmp.ru



пионовидные розы цена