681. The Skyline Problem

0

Easy

Given the locations and heights of buildings in a city, determine the skyline formed by these buildings when viewed from a distance. The geometric information of each building is provided in the array buildings, where buildings[i] = [left[i], right[i], height[i]]: 1. left[i] represents the x-coordinate of the left edge of the ith building. 2. right[i] represents the x-coordinate of the right edge of the ith building. 3. height[i] represents the height of the ith building. Assume all buildings are perfect rectangles grounded on a flat surface at height 0. Represent the skyline as a list of "key points" sorted by their x-coordinate in the form [[x1,y1],[x2,y2],...]. Each key point represents the left endpoint of a horizontal segment in the skyline, except for the last point in the list, which always has a y-coordinate of 0 and marks the end of the skyline where the rightmost building ends. Include any ground between the leftmost and rightmost buildings as part of the skyline's contour. **Note**: The output skyline should not contain consecutive horizontal lines of equal height. Merge any consecutive lines of equal height into one in the final output.

Input Format

The first line contains the number of buildings, N.
The second line contains 5xN integers representing the locations and heights of the buildings.

Output Format

Print a 2-D array.

Example

Input

2 0 2 3 2 5 3

Output

0 3 5 0

Constraints

1 <= buildings.length <= 10^4
0 <= lefti < righti <= 231 - 1
1 <= heighti <= 231 - 1
buildings is sorted by left[i] in non-decreasing order.