CSG-CPC Online Judge

1183 : 消除隐藏线

         Time Limit: 1 Sec     Memory Limit: 128 Mb     Submitted: 144     Solved: 45    

Description

在计算机辅助设计(CAD)中,有一个经典问题:消除隐藏线(被其它图形遮住的线段)。你需要设计一个软件,帮助建筑师绘制城市的侧视轮廓图。为了方便处理,限定所有的建筑物都是矩形的,而且全部建立在同一水平面上。每个建筑物用一个三元组表示(Li, Hi, Ri)其中 Li 和 Ri 分别是建筑物 i 的左右边缘坐标,Hi 是建筑物 i 的高度。

下面左图中的建筑物分别用如下三元组表示:

(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)

Input

多组测试数据,每组数据第一行整数 n 表示建筑物三元组个数。

接下来 n 行,每行 3 个整数表示一个建筑物的三元组 (Li, Hi, Ri) 。建筑物的坐标都是正整数且不大于 1000

三元组按 Li 从小到大顺序给出,即左边缘坐标最小的建筑物三元组会出现在每组数据的第一个。

1 <= n <= 50

Output

每组数据输出一行描述轮廓线的数值序列,其中偶元素代表轮廓线的延伸高度,奇元素代表轮廓线顶点的水平坐标,如上面的图例所示。

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

Sample Output

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

Hint