题目描述

Ricardo 是一名餐厅评论家，这意味着他花时间在餐厅用餐并给出评分。每个评分是一个介于 $0$ 到 $3$（含）之间的整数星数。因此，总共有恰好四种可能的评分。

在他访问 Cheapland 期间，他必须评价 $N$ 家餐厅。不幸的是，所有这些餐厅都很糟糕，如果任由 Ricardo 表达真实意见，他会给每家餐厅都打 $0$ 星。然而，Cheapland 的政$$府可以贿赂 Ricardo 来提高任何一家餐厅的评分。

每家餐厅都有自己的贿赂成本，这既取决于餐厅本身，也取决于获得的星数。贿赂 Ricardo 给一家餐厅 $3$ 星总是比贿赂他给 $2$ 星更昂贵，而贿赂 $2$ 星又比贿赂 $1$ 星更昂贵。自然，$0$ 星评分不需要任何支付。

正如人们可能想象的那样，Cheapland 政$$府希望在使他们的美食景观看起来尽可能强大的同时，花费尽可能少的钱。为了规划他们的策略，他们需要确定在所有 $N$ 家餐厅中总共获得 $k$ 颗星所需的最小成本，其中 $k$ 是 $1$ 到 $3N$（含）之间的每个整数值。

然而，由于贿赂成本因餐厅而异，计算这些值并不简单——这就是他们需要你帮助的原因。

输入格式

第一行包含一个整数 $N$（$1 \le N \le 2 \cdot 10^5$），表示餐厅的数量。

接下来的 $N$ 行，每行描述一家餐厅，包含三个整数 $C_1$、$C_2$ 和 $C_3$（$1 \le C_1 < C_2 < C_3 \le 10^9$），其中 $C_i$ 表示让该餐厅获得 $i$ 星评分的成本。

输出格式

对于每个从 $1$ 到 $3N$（含）的 $k$，输出一行，包含一个整数，表示在所有 $N$ 家餐厅中恰好总共获得 $k$ 颗星所需的最小总成本。

3
1 2 3
2 10 11
5 6 7

1
2
3
5
9
10
12
20
21

4
999999998 999999999 1000000000
999999998 999999999 1000000000
999999998 999999999 1000000000
999999998 999999999 1000000000

999999998
999999999
1000000000
1999999998
1999999999
2000000000
2999999998
2999999999
3000000000
3999999998
3999999999
4000000000

提示

翻译由 DeepSeek V3 完成