ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

2075. Берегите брови!

Ограничение времени: 1.0 секунды
Ограничение памяти: 256 МБ
Олег пришёл в бар и заказал себе шот. Шот — коктейль из нескольких ликёров, который наливают в стеклянную цилиндрическую стопку и затем пьют через трубочку. Некоторые ликёры поджигают или предварительно подогревают. Шот является слоистым коктейлем, то есть ликёры в стопке располагаются слоями и не смешиваются друг с другом.
Бармен поочерёдно берёт нужные ликёры и наливает их в стопку. Бармен наливает каждый следующий слой мгновенно. Ликёр мгновенно просачивается сквозь все ликёры с меньшей плотностью, если такие есть в стопке. Если нет, то этот ликёр остаётся сверху. И в том, и в другом случае если в коктейле уже был такой ликёр, то весь он объединяется в один слой.
Олегу не терпится попробовать этот божественный напиток, поэтому он может начать пить его раньше, чем бармен закончит наливать все ингредиенты. Также время от времени Олег может переносить трубочку на другую глубину или обжигаться и переставать пить.
За одну секунду Олег выпивает объём жидкости высотой в один миллиметр. Как только на этой высоте не останется жидкости, Олег перестанет пить. Но если в точности в этот момент бармен нальёт ликёр, то Олег не остановится, а продолжит пить дальше. Добавление новых ликёров и питьё коктейля не влияют на положение трубочки. Стопка достаточно высокая и не переполняется при добавлении новых ликёров. Объёмом трубочки можно пренебречь. Гарантируется, что жидкость горит достаточно медленно, чтобы не учитывать уменьшение её объёма по этой причине.

Исходные данные

В первой строке дано целое число n (1 ≤ n ≤ 105) — количество событий. Далее в n строках описаны события. События бывают трёх типов:
  1. T name h — в момент времени T бармен наливает слой ликёра name высотой h миллиметров;
  2. T Oleg H — в момент времени T Олег опустил трубочку на высоту H от дна стопки и начал или продолжил пить. Гарантируется, что в этот момент высота жидкости в стопке больше H;
  3. T fire — в момент времени T Олег обжёгся и достал трубочку. Гарантируется, что с момента времени T−1 до момента времени T Олег пил.
name — непустая строка из строчных латинских букв длины не более 10. T, H и h целые; 0 ≤ T ≤ 109; 0 ≤ H ≤ 1014; 1 ≤ h ≤ 109. Все времена T различны и упорядочены по возрастанию. Плотности всех ликёров различны. Плотность ликёра тем больше, чем лексикографически меньше его название. Ликёра с названием «fire» нет.

Результат

Выведите промежутки времени, в которые Олег пьёт ликёр, с указанием, какой именно. Следуйте формату вывода, указанному в примере. Все промежутки должны следовать по возрастанию времени. Для двух соседних промежутков либо должны различаться названия ликёров, либо первый должен заканчиваться строго раньше, чем начинается второй.

Пример

исходные данныерезультат
7
1 kahlua 1
2 baileys 1
3 cointreau 1
4 Oleg 0
5 kahlua 3
6 fire
20 Oleg 0
4-5 baileys
5-6 cointreau
20-24 kahlua

Замечания

В жизни калуа самый тяжёлый, но в данной задаче пусть вас это не смущает, пример верный.
Автор задачи: Михаил Рубинчик (Подготовка — Егор Щелконогов)