Description

There are $n$ buildings on the horizon (the $x$ axis), and each building is represented as a rectangle.

The $i$-th rectangle is represented by three integers $h_i, l_i, r_i$: its bottom-left corner is at $(l_i, 0)$ and its top-right corner is at $(r_i, h_i)$.

The horizon has height $0$. Subject to minimizing the skyline polyline length (i.e., without redundant points), output the skyline from left to right.

Input Format

The first line contains an integer $n$, the number of rectangles.

Each of the following $n$ lines contains $3$ integers $h_i, l_i, r_i$ describing the $i$-th rectangle.

Output Format

The first line contains an integer $m$, the number of nodes.

Each of the following $m$ lines contains one coordinate, representing a node on the skyline.

Traverse the skyline from left to right and output the nodes in order.

Note: The $y$-coordinates of the first and the last node are both $0$.

2
3 0 2
4 1 3

6
0 0
0 3
1 3
1 4
3 4
3 0

5
3 -3 0
2 -1 1
4 2 4
2 3 7
3 6 8

14
-3 0
-3 3
0 3
0 2
1 2
1 0
2 0
2 4
4 4
4 2
6 2
6 3
8 3
8 0

Hint

Sample 2 as shown:

Constraints:

For $30\%$ of the testdata, $n \le 100$.

For another $30\%$ of the testdata, $1 \le h_i, l_i, r_i \le 1000$.

For $100\%$ of the testdata, $1 \le n \le 10^5$, $1 \le h_i \le 10^9$, $-10^9 \le l_i < r_i \le 10^9$.

Translated by ChatGPT 5