The Skyline Problem

Given a set of buildings in a city's skyline, each represented by a triplet ( (L, R, H) ) where (L) is the left x-coordinate, (R) is the right x-coordinate, and (H) is the height, your task is to compute the key points that form the skyline. The skyline is defined by the outer contour formed by the union of all the buildings. A key point is a point where the height of the skyline changes.

For example, a single building ( (L, R, H) ) results in a skyline with key points ( (L, H) ) and ( (R, 0) ). In the case of overlapping buildings, the skyline will change at the points where one building overtakes or ends relative to another.

Formally, if you denote the current maximum height at any x-coordinate by ( h(x) ), then the key points are the set of coordinates ( (x, h(x)) ) where ( h(x) ) changes. Your solution should compute these key points in increasing order of x-coordinate.

inputFormat

The input is read from standard input (stdin). The first line contains an integer ( n ) representing the number of buildings. Each of the following ( n ) lines contains three space-separated integers ( L ), ( R ), and ( H ), which represent the left coordinate, right coordinate, and height of a building, respectively.

outputFormat

Output the key points of the skyline to standard output (stdout). Each line should contain two integers: the x-coordinate and the height at that point. The key points should be printed in increasing order of x-coordinate. There should be no extra spaces or blank lines.## sample

1
1 5 11

1 11
5 0