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.

In the first line you are given an integer n (1 ≤ n ≤ 10⁵) — the number of events. In the next n lines there are events’ descriptions. Each event can be one of three types:

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 ≤ 10⁹; 0 ≤ H ≤ 10¹⁴; 1 ≤ h ≤ 10⁹. 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 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.

In real life kahlua is the heaviest liqueur but this fact should not confuse you.