题目描述

Ricardo is a restaurant critic, which means he spends his time eating at restaurants and giving them a rating. Each rating is an integer number of stars between $0$ and $3$, inclusive. Thus, there are exactly four possible ratings.

During his visit to Cheapland, he must review $N$ restaurants. Unfortunately, all of them are terrible, and if left to his honest opinion, Ricardo would give $0$ stars to every restaurant. However, the government of Cheapland can bribe Ricardo to increase the rating of any restaurant.

Each restaurant has its own bribe costs, which depend both on the restaurant itself and on the number of stars awarded. Bribing Ricardo to give a restaurant $3$ stars is always more expensive than bribing him for $2$ stars, which in turn is more expensive than bribing him for $1$ star. Naturally, no payment is required for a $0$-star rating.

As one might imagine, the Cheapland government wants to spend as little as possible while making their gastronomic scene look as strong as possible. To plan their strategy, they need to determine the minimum cost required to achieve a total of $k$ stars among all the $N$ restaurants, for every integer value $k$ between $1$ and $3N$, inclusive.

However, since bribe costs vary from restaurant to restaurant, calculating these values isn’t straightforward – which is why they need your help.

输入格式

The first line contains an integer $N$ ($1 \le N \le 2 \cdot 10^5$) indicating the number of restaurants.

Each of the next $N$ lines describes a restaurant with three integers $C_1$, $C_2$ and $C_3$ ($1 \le C_1 < C_2 < C_3 \le 10^9$), where $C_i$ is the cost of getting a rating of $i$ stars for the restaurant.

输出格式

Output a line for each $k$ from $1$ to $3N$ (inclusive), with an integer indicating the minimum total cost required to achieve exactly $k$ stars among all the $N$ restaurants.

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