Gapcheon 是一条流经大德科学城（Daedeok Innopolis）的河流。大德科学城是位于大田的一个研究区，其中包括韩国科学技术院（KAIST）、世博科学公园、国立中央科学馆等。Gapcheon 的滨水区被用作公园，是休闲娱乐的场所。

在本题中，我们将 Gapcheon 建模为一条略微弯曲的弧线。在这条弧线上，每隔一厘米标记了恰好 $10^6$ 个点。在 Gapcheon 上有 $N$ 座桥，每座桥连接弧线上的两个不同点，表现为一条直线段。这样的线段可以在端点处接触其他线段，但除此之外绝不相交。对于每一对点，至多存在一座直接连接这两点的桥。

图 1. 阴天下的 Gapcheon 和一座世博桥

图 2. $x, y, z$ 是互不相交但仅在端点处接触的桥。这可能是一个合法的输入实例。编号为 $8 \dots 10^6$ 的点为简洁起见已省略。

图 3. $x, y$ 是相互交叉的桥。这不是一个合法的输入实例。编号为 $8 \dots 10^6$ 的点为简洁起见已省略。

市政府计划在桥上安装一些灯光，使 Gapcheon 在夜晚更加宜人。对于每座桥，市政府计算了如果安装灯光所能带来的美学价值。这些价值可以用正整数表示。

然而，过多的灯光会在午夜打扰居民。为了解决这个问题，市政府决定制定一些规定：对于连接两个相邻点的每一段弧，可见的亮灯桥梁数量应至多为 $k$ 座。如果一条线段的一个端点索引小于等于 $i$，且另一个端点索引大于等于 $i+1$，则称该线段从连接 $i, i+1$ 的弧处可见。

市政府希望权衡光污染与夜景，因此你需要针对所有整数 $1 \le k \le N$，分别求出美学价值之和的最大值。

输入格式

第一行包含一个整数 $N$ ($1 \le N \le 250\,000$)。

接下来的 $N$ 行包含三个整数 $S_i, E_i, V_i$，表示有一座连接点 $S_i$ 和 $E_i$ 的直线桥，其美学价值为 $V_i$ ($1 \le S_i < E_i \le 10^6, 1 \le V_i \le 10^9$)。

保证没有线段连接同一对点，且没有两条不同的线段相交。

输出格式

输出 $N$ 个整数，用空格分隔。第 $i$ 个整数 ($1 \le i \le N$) 应为 $k=i$ 时的答案。

样例

样例输入 1

6
1 2 10
2 3 10
1 3 21
3 4 10
4 5 10
3 5 19

样例输出 1

41 80 80 80 80 80

样例输入 2

4
1 5 1
2 5 1
3 5 1
4 5 1

样例输出 2

1 2 3 4

说明

图 4. 样例 1 的示意图。