Олег пришёл в бар и заказал себе шот. Шот — коктейль из нескольких ликёров, который наливают в стеклянную цилиндрическую стопку и затем пьют через трубочку. Некоторые ликёры поджигают или предварительно подогревают. Шот является слоистым коктейлем, то есть ликёры в стопке располагаются слоями и не смешиваются друг с другом.

Бармен поочерёдно берёт нужные ликёры и наливает их в стопку. Бармен наливает каждый следующий слой мгновенно. Ликёр мгновенно просачивается сквозь все ликёры с меньшей плотностью, если такие есть в стопке. Если нет, то этот ликёр остаётся сверху. И в том, и в другом случае если в коктейле уже был такой ликёр, то весь он объединяется в один слой.

Олегу не терпится попробовать этот божественный напиток, поэтому он может начать пить его раньше, чем бармен закончит наливать все ингредиенты. Также время от времени Олег может переносить трубочку на другую глубину или обжигаться и переставать пить.

За одну секунду Олег выпивает объём жидкости высотой в один миллиметр. Как только на этой высоте не останется жидкости, Олег перестанет пить. Но если в точности в этот момент бармен нальёт ликёр, то Олег не остановится, а продолжит пить дальше. Добавление новых ликёров и питьё коктейля не влияют на положение трубочки. Стопка достаточно высокая и не переполняется при добавлении новых ликёров. Объёмом трубочки можно пренебречь. Гарантируется, что жидкость горит достаточно медленно, чтобы не учитывать уменьшение её объёма по этой причине.

В первой строке дано целое число n (1 ≤ n ≤ 10⁵) — количество событий. Далее в n строках описаны события. События бывают трёх типов:

name — непустая строка из строчных латинских букв длины не более 10. T, H и h целые; 0 ≤ T ≤ 10⁹; 0 ≤ H ≤ 10¹⁴; 1 ≤ h ≤ 10⁹. Все времена T различны и упорядочены по возрастанию. Плотности всех ликёров различны. Плотность ликёра тем больше, чем лексикографически меньше его название. Ликёра с названием «fire» нет.

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

В жизни калуа самый тяжёлый, но в данной задаче пусть вас это не смущает, пример верный.