Ricardo 是一位餐厅评论家，这意味着他花费时间在餐厅用餐并给出评分。每个评分都是 0 到 3 之间的整数（包含 0 和 3）。因此，总共有四种可能的评分。

在访问 Cheapland 期间，他必须评价 $N$ 家餐厅。不幸的是，这些餐厅都很糟糕，如果完全按照他的真实评价，Ricardo 会给每家餐厅打 0 分。然而，Cheapland 政府可以贿赂 Ricardo 以提高任何餐厅的评分。

每家餐厅都有其各自的贿赂成本，这取决于餐厅本身以及所授予的星级。贿赂 Ricardo 给一家餐厅打 3 分总是比打 2 分更贵，而打 2 分又比打 1 分更贵。当然，0 分不需要支付任何费用。

可以想象，Cheapland 政府希望在尽可能少花钱的同时，让他们的餐饮业看起来尽可能强大。为了规划策略，他们需要确定在所有 $N$ 家餐厅中获得总计 $k$ 颗星所需的最低成本，对于 $1$ 到 $3N$ 之间的每个整数 $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$（包含 $1$ 和 $3N$），输出一行，包含一个整数，表示在所有 $N$ 家餐厅中获得总计恰好 $k$ 颗星所需的最低总成本。

样例

样例输入 1

3
1 2 3
2 10 11
5 6 7

样例输出 1

1
2
3
5
9
10
12
20
21

样例输入 2

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

样例输出 2

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