ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

Qualification round of Eastern subregional contest 2015

About     Problems     Submit solution     Judge status     Standings
Contest is over

B. Take care of your eyebrows!

Time limit: 1.0 second
Memory limit: 256 MB
Once upon a time Oleg came to bar and ordered a shot cocktail. A shot cocktail consists of several liqueurs. One fills a cylindric glass with liqueurs and drinks the cocktail through a straw. Some liqueurs are fired or warmed up. Liqueurs form layers and do not mix with each other.
Barman pours required liqueurs to a glass in order. He pours every layer instantly. The new liqueur percolates through all layers with lower density instantly if there are any. Otherwise this liqueur remains at the top. In any case if the cocktail has the same liqueur already then both layers of this liqueur unite into one layer.
Oleg is eager to taste this divine beverage so he can even start to drink it until barman finishes pouring of all ingredients. Sometimes Oleg can also move his straw to another height or burn himself and stop drinking.
In one second Oleg drinks one millimeter of the cocktail. Oleg stops drinking as soon as there is no cocktail on the current height. But in case barman pours the liqueur exactly at this moment Oleg continues drinking. Pouring of new liqueurs and drinking do not change the height of a straw. The glass is high enough not to be overfilled. The volume of a straw can be neglected. You can assume that the liqueurs burn slowly enough so you can neglect associated volume decreasing.

Input

In the first line you are given an integer n (1 ≤ n ≤ 105) — the number of events. In the next n lines there are events’ descriptions. Each event can be one of three types:
  1. T name h — at the moment T barman pours the layer of the liqueur name with height of h millimeters.
  2. T Oleg H — at the moment T Oleg sets the straw’s height to H millimeters from the bottom and starts or continues drinking. You can assume that the current cocktail’s height is greater than H.
  3. T fire — at the moment T Oleg burns himself and takes out his straw. You can assume that Oleg is drinking between time moments T−1 and T.
name is non-empty string with length less than or equal to 10 which consists of lowercase latin letters. T, H and h are integers; 0 ≤ T ≤ 109; 0 ≤ H ≤ 1014; 1 ≤ h ≤ 109. All time moments T are different and sorted in ascending order. Densities of all liqueurs are different. The density of the liqueur is greater if and only if its name is lexicographically less. There is no liqueur named «fire».

Output

Output time intervals when Oleg drinks a liqueur specifying its name. Follow the sample output format. All time intervals should be sorted in ascending order. Any two neighboring intervals should have different names or the first one should finish strictly earlier than the second one starts.

Sample

inputoutput
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

Notes

In real life kahlua is the heaviest liqueur but this fact should not confuse you.
Problem Author: Mikhail Rubinchik (prepared by Egor Shchelkonogov)
To submit the solution for this problem go to the Problem set: 2075. Take care of your eyebrows!