City Skyline

You are given a list of buildings in the province of Latium. Each building is described by a triple \( (L_i, H_i, R_i) \), where \( L_i \) and \( R_i \) denote the left and right x-coordinates of the building respectivly, and \( H_i \) denotes the height of the building. All buildings stand on a flat horizontal ground.

Your task is to compute the skyline of the city formed by these buildings. The skyline is represented as a list of key points. A key point is defined as a coordinate \( (x, h) \) where the height of the skyline changes. The final key point must have a height of 0. For example, if the skyline changes at x-coordinates and heights as shown below, it is represented by the sequence:

[ (1, 11),\ (3, 13),\ (9, 0),\ (12, 7),\ (16, 3),\ (19, 18),\ (22, 3),\ (23, 13),\ (29, 0) ]

Output the sequence as space separated numbers: 1 11 3 13 9 0 12 7 16 3 19 18 22 3 23 13 29 0.

Note: Use an efficient algorithm to handle multiple buildings and overlapping intervals.

inputFormat

The input begins with an integer \( n \) representing the number of buildings. Each of the following \( n \) lines contains three space-separated integers \( L_i \), \( H_i \), and \( R_i \) that represent the left coordinate, height, and right coordinate of a building respectively.

Example:

8
1 11 5
2 6 7
3 13 9
12 7 16
14 3 25
19 18 22
23 13 29
24 4 28

outputFormat

Output the skyline as a sequence of space separated integers. Each pair of integers represents the x coordinate and the height at that coordinate where the skyline changes. The last pair should always have height 0.

For the sample input above, the output should be:

1 11 3 13 9 0 12 7 16 3 19 18 22 3 23 13 29 0

sample

8
1 11 5
2 6 7
3 13 9
12 7 16
14 3 25
19 18 22
23 13 29
24 4 28

1 11 3 13 9 0 12 7 16 3 19 18 22 3 23 13 29 0