The Skyline Problem

Given a list of buildings, each represented as a triplet of integers (start, end, height), compute the skyline formed by these buildings. The skyline is the outer contour of these buildings when viewed from a distance. In other words, output the key points where the height changes along the horizontal axis. Two events occur: a building's start contributes a rise (its height is added) and a building's end contributes a drop (its height is removed).

The problem can be formalized as follows. Let \(B = [(L_1, R_1, H_1), (L_2, R_2, H_2), \dots, (L_n, R_n, H_n)]\) be the list of buildings. You are to compute a sequence of key points \(K = [(x_1,h_1),(x_2,h_2),\dots,(x_k,h_k)]\) such that:

• The first key point is at the leftmost x position with a nonzero height.
• The last key point is where the skyline drops to zero.
• A new key point is added whenever the maximum height among the active buildings changes.

Your goal is to determine these key points given the list of buildings.

inputFormat

The input is read from stdin and has the following format:

1. An integer n representing the number of buildings.
2. Followed by n lines, each containing three space‐separated integers: start end height, where start and end denote the x-coordinates at which the building begins and ends, and height is the height of the building.

outputFormat

The output is written to stdout and consists of several lines. Each line represents a key point of the skyline in the format:

x height

The key points must describe the critical changes in the skyline.

## sample

1
1 3 3

1 3
3 0

</p>