TopCoder

User's AC Ratio

79.1% (34/43)

Submission's AC Ratio

41.1% (69/168)

Description

地平線上有許多房子,而這些房子在夕陽的照射之下形成有趣的輪廓,我們稱之為天際線(Skyline)。

為了方便起見,你可以假設所有的房子都是一個位在2D平面上的矩形,並且有一條邊貼在這個假想2D平面上的X軸。

一棟建築可以用三元數組(Li,Hi,Ri)來表示,依序代表該建築物的左界座標、高度、右界座標。下方左圖中的八棟建築就是用此方法表示就是(1,11,5), (2,6,7), (3,13,9), (12,7,16), (14,3,25), (19,18,22), (23,13,29), (24,4,28)。

一個天際線也可以用類似的「X-遞增序列」表示出來,例如上面的八棟建築合併之後上方右圖的天際線可表示為:
(1, 11, 3, 13, 9, 0, 12, 7, 16, 3, 19, 18, 22, 3, 23, 13, 29, 0)

請你寫一個程式,給你這些房子的位置,請你把它們形成的天際線描述出來。

Input Format

輸入檔可能包含多筆測試資料。
每筆測試資料的第一列有一個正整數n(1<=n<=30,000),然後有n列,每列有三個整數Li,Hi,Ri用來描述一棟建築(Li<Ri)。所有數字都介於1和109之間(包含1以及109)。
當n=0時,代表輸入結束,請不要對它做任何處理。

Output Format

對於每一筆測試資料,請按照題目以及範例輸出格式輸出天際線的樣子。請注意,最後一個數字一定是0。也請不要輸出多餘空白。

※請保證你的輸出是所有天際線的描述當中最簡短的。
例如:(1, 100, 2, 100, 3, 100, 4, 0)是不正確的,因為X座標在1,2之間、2,3之間、3,4之間的高度都是100,沒有必要描述出來。
上面例子的正確輸出是(1, 100, 4, 0)。

Sample 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
0

Sample Output

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

Hints

Problem Source

原TIOJ1202 / TIOJ 2008例行賽02 (prob D)。adapted from: ACM 105。Problem Setter:Tmt。

Subtasks

For Testdata: 0 ~ 0, Score: 50
For Testdata: 1 ~ 1, Score: 50
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1000 65536 262144
1 1000 65536 262144