Under construction

Still being built. Things may change

Skyline

Time limit2sMemory limit128 MB

Summary
Given up to 100,000 rectangular buildings, compute the merged skyline as a sequence of x-coordinate and height key points using a sweep with a heap.
Level

Medium7 of 10

Topics
Heap, Sorting, Divide and conquer
Solved
No attempts yet

Problem

Given N rectangular buildings, compute the skyline formed by their union. Each building is described by its left x-coordinate L, height H, and right x-coordinate R, and all buildings stand on the same ground line.

The skyline is the outer outline of the rectangles when they are viewed together. Report every point where the visible height changes, from left to right.

Input

The first line contains the number of buildings N (1 <= N <= 100,000).

Each of the next N lines contains three integers L, H, and R, describing one building's left x-coordinate, height, and right x-coordinate.

The coordinates and heights satisfy 1 <= L < R <= 1,000,000,000 and 1 <= H <= 1,000,000,000.

Output

Print the skyline on one line. For each point where the height changes, print the x-coordinate of that point followed by the height from that point onward. Separate all values with spaces.

Examples1

  1. Example 1

    Input
    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
    Expected output
    1 11 3 13 9 0 12 7 16 3 19 18 22 3 23 13 29 0