题目描述

Nicolae 想忘掉一张旧照片。照片中有 $n$ 个特殊像素，每个特殊像素位于整数坐标处，并带有一个整数权值，表示 Nicolae 看到它时产生的悲伤值。

为了让自己好过一些，Nicolae 想把照片切成 $4$ 个部分。他会选择一个点

$$P=(x+0.5,y+0.5),$$

其中 $x,y$ 都是整数，然后沿经过点 $P$ 且平行于坐标轴的两条直线切开照片。

切开后得到的四个部分记为 $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))$$

天才能忘记它。

现在，对于每个 $x\in\{1,2,\ldots,n-1\}$，Nicolae 固定要求切割点 $P$ 位于竖直直线 $X=x+0.5$ 上。你需要求出此时通过选择最优的 $y$，能得到的最少悲伤天数。

输入格式

第一行包含一个整数 $n$。

接下来 $n$ 行，每行包含三个整数 $x_i,y_i,s_i$，表示一个特殊像素的横坐标、纵坐标和悲伤值。

一些特殊像素可以位于相同坐标。

输出格式

输出 $n-1$ 个整数。对于每个 $x\in\{1,2,\ldots,n-1\}$，输出当切割点 $P$ 位于竖直直线 $X=x+0.5$ 上时，Nicolae 忘记照片所需的最少悲伤天数。

数据范围

• $2\le n\le 2\cdot 10^5$；
• $1\le x_i,y_i\le n$；
• $1\le s_i\le 10^9$。

样例 1

输入

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

输出

9
3
9