Skyline Problem

Given \(n\) buildings on the horizon (\(x\)-axis), each building is represented by a rectangle defined by three integers \(h_i\), \(l_i\), and \(r_i\): the lower left corner is at \((l_i, 0)\) and the upper right corner is at \((r_i, h_i)\). The horizon is at height 0. Your task is to compute the skyline (contour) from left to right such that the contour path is as short as possible, i.e. it contains no redundant points.

The skyline is defined as the key points where the height changes. For example, if the key points are \((x_1,h_1), (x_2,h_2), \ldots, (x_k,h_k)\), then these points uniquely determine the outline of the union of the rectangles.

inputFormat

The first line contains an integer \(n\) representing the number of buildings. Each of the following \(n\) lines contains three space-separated integers \(h_i\), \(l_i\), and \(r_i\) — the height, left coordinate, and right coordinate of the \(i\)-th building, respectively.

outputFormat

Output the skyline as a sequence of key points. For each key point, print the \(x\)-coordinate and the height, separated by a space. All key points should be printed on one line with a single space between numbers. There should be no trailing spaces.

For example, if the skyline is defined by key points \((x_1,h_1), (x_2,h_2), \ldots, (x_k,h_k)\), then the output should be:

x₁ h₁ x₂ h₂ ... xₖ hₖ

sample

1
3 1 3

1 3 3 0