Nicolae 和他的女朋友 Cristina 分手了，现在他想忘掉所有和她有关的照片。在这些照片中，有一张非常特殊的照片，上面有 $n$ 个位于整数坐标上的特殊像素。对于这些像素中的每一个，Nicolae 都分配了一个整数值，用来描述他看着它时感受到的悲伤程度。

Nicolae 很沮丧，他想把这张照片切成 4 个部分。为此，他将选择一个点 $P = (x + 0.5, y + 0.5)$，其中 $x$ 和 $y$ 为整数。然后，他将沿着穿过点 $P$ 且平行于坐标轴的直线切割照片。

Nicolae 将得到的 4 个部分称为 $A, B, C$ 和 $D$。对于一个部分 $X$，他定义 $S(X)$ 为该部分的悲伤总值，即该部分内所有特殊像素的悲伤值之和。

Nicolae 需要花费 $\max(S(A), S(B), S(C), S(D)) - \min(S(A), S(B), S(C), S(D))$ 天的悲伤时间才能忘掉这张照片，因此最优地选择点 $P$ 可以让他少受很多痛苦。

对于每个 $x \in \{1, 2, \dots, n-1\}$，Nicolae 想知道，如果他选择点 $P$ 在坐标为 $x + 0.5$ 的垂直线上，他忘掉这张照片所需的最少悲伤天数是多少。

输入格式

第一行包含一个整数 $n$ ($2 \le n \le 2 \cdot 10^5$)。

接下来的 $n$ 行，每行包含三个整数 $x_i, y_i, s_i$ ($1 \le x_i, y_i \le n$ 且 $1 \le s_i \le 10^9$)，分别表示每个特殊像素的坐标和悲伤值。部分像素可能重合。

输出格式

输出包含 $n-1$ 个整数：对于每个 $x \in \{1, 2, \dots, n-1\}$，输出如果选择点 $P$ 在坐标为 $x + 0.5$ 的垂直线上时，Nicolae 忘掉照片所需的最少悲伤天数。

样例

样例输入 1

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

样例输出 1

9
3
9