The Skyline Problem

Given a list of buildings in a city, each building is represented by a triplet ((L, R, H)) where (L) is the left coordinate, (R) is the right coordinate (with (L < R)), and (H) is the height of the building. The skyline is the outer contour formed by these overlapping buildings. Your task is to compute the list of key points that uniquely defines this skyline. A key point is a position where the height of the skyline changes. This is a typical computational geometry problem that can be solved using a sweep line algorithm with a priority queue (heap).

Input is provided via standard input and output should be printed to standard output. The first line contains an integer (n) representing the number of buildings. Each of the following (n) lines contains three integers: (L), (R), and (H). The output should contain the critical points of the skyline in order from left to right, with each point printed on a separate line as two space-separated integers (the x-coordinate and the height).

inputFormat

The input begins with a single integer (n) on the first line representing the number of buildings. This is followed by (n) lines, each containing three space-separated integers (L), (R), and (H), where (L) is the left coordinate, (R) is the right coordinate, and (H) is the height of a building.

outputFormat

Output the critical points of the skyline from left to right. Each key point is represented by two integers: the x-coordinate and the corresponding height, printed on a separate line.## sample

5
2 9 10
3 7 15
5 12 12
15 20 10
19 24 8

2 10
3 15
7 12
12 0
15 10
20 8
24 0