0144. Artist

One very enterprising artist has developed brand new impressionist style called "1-dimension impressionism". The painting which brought him $1'000'000 was entitled "The Black Line". Obviously "The White Line" brought him another million. Now his is too tired pursuing pirate DVD copies of his masterpieces, so he has put aside his work on 254 variations of "The Gray Line" and wants to create a picture which will be way hard to copy. Since he is a very rich artist, he does not use the brush, instead uses PaintBrush and a special computer with a very special monitor. As you may already have guessed – it is 1-dimensional 2km long monitor. His paintings are described as a sequence of color segments drawn one over another. Now he wants to know the amount of each color in the final picture (of course, to order the proper screen saver).

Input file

The first line has the only number k which stands for the number of color segments painted. 0 ≤ k ≤ 100'000. k lines follow, each in format a b c where -10⁹ ≤ a, b ≤ 10⁹ are the line segment endpoints. 0 ≤ c ≤ 1'000'000'000 is the color index. Limits for a and b stated above declare not only monitor coordinate bounds but also precision for these values in the input. No two color indices refer to the same color, so you may consider color index as the color itself. By the way, this assumption arises not only from simplicity; the artist did not distinguish colors, only brightness. Initially the painting is completely black (color index 1'000'000'000 since he also saw all colors inverted; but nobody knows how to prove that). Each new line segment changes color of the painting between its endpoints to the new color. The segments are given in the order they were painted.

Output file

Several lines in format c s where c is the color index and s is the total linear volume this color occupies. You must list final colors in ascending order of c and you must not list the black color and colors having s = 0. Value of s must be given with as few digits after the decimal point as possible. If s for particular color is integer, it must be given in integer format

Examples: