The Skyline Problem

Given a list of buildings, compute the skyline formed by these buildings. Each building is represented by a triplet \( (L, R, H) \), where \(L\) and \(R\) denote the x-coordinates of the left and right edges, and \(H\) is the height.

The skyline is a list of key points \( (x, height) \) that uniquely defines the outer contour of the group of buildings. A key point is a point where the height of the skyline changes.

Input/Output Requirements:

• The input is provided from standard input (stdin) and the output should be printed to standard output (stdout).
• You must output each key point on a new line with the x-coordinate and height separated by a space.

Note: If two events occur at the same x coordinate, a starting event should be processed before an ending event. All formulas are rendered in LaTeX format.

inputFormat

The first line contains an integer \(N\), the number of buildings. Next \(N\) lines follow, each containing three space-separated integers \(L\), \(R\), and \(H\) representing a building.

Example:

2
1 3 4
2 4 3

outputFormat

The output consists of several lines. Each line contains two space-separated integers: the x-coordinate and the height of a key point of the skyline. The sequence of key points should represent the skyline formed by the buildings.

Example:

1 4
3 3
4 0

## sample

2
1 3 4
2 4 3

1 4
3 3
4 0

</p>