Description

Genoa in the province of Latium is a stretch of land at the northern end of the west coast of the Apennine Peninsula, rich in natural resources yet uninhabited. You are commissioned by the Roman consul Caesar to go to Genoa and build a new city. Caesar’s requirement for this task is to establish a prosperous city on this land in Genoa, and he will use this as the standard to evaluate your performance.

While you are vigorously carrying out city construction, Caesar suddenly writes to you saying he wants to inspect the progress in Genoa. Caesar wants to know what your city looks like, but he is very busy, so he only needs you to describe the city’s skyline; he will decide your salary based on this skyline.

How to describe a city’s skyline? We know that all buildings in Genoa share a ground level, which you can consider horizontal. Each building is represented by a triple $(L_i,H_i,R_i)$, where $L_i$ and $R_i$ are the left and right coordinates of the building, and $H_i$ is the building’s height. In the figure below, the buildings on the left are described as $(1,11,5)$, $(2,6,7)$, $(3,13,9)$, $(12,7,16)$, $(14,3,25)$, $(19,18,22)$, $(23,13,29)$, $(24,4,28)$, and the skyline on the right is represented by the sequence $(1,11,3,13,9,0,12,7,16,3,19,18,22,3,23,13,29,0)$:

Input Format

You will be given a series of triples representing buildings. All coordinate values in the input are positive integers less than $10000$. There is at least $1$ building and at most $5000$ buildings. Each building’s triple occupies one line. All integers in a triple are separated by one or more spaces.

Output Format

Output the skyline of the city. Describe it as follows: list all key points on the skyline in order; output the $x$ coordinate for odd-numbered entries and the $y$ coordinate for even-numbered entries, with a space between two numbers.

1 11 5
2 6 7
3 13 9
12 7 16
14 3 25
19 18 22
23 13 29
24 4 28

1 11 3 13 9 0 12 7 16 3 19 18 22 3 23 13 29 0

Hint

Translated by ChatGPT 5