Problem Description

New AtCoder City is structured like an infinite grid.

• At the center of New AtCoder City, there is a clock tower, and its coordinates are $ (0, 0) $.
• There is a straight road running east-west through the clock tower, which is called the "East-West Avenue". This corresponds to the $ x $-axis on a 2D coordinate plane.
• Additionally, there are infinitely many roads parallel to the East-West Avenue, spaced 1 unit apart. These correspond to the lines $y = (integer \neq 0)$.
• There is a straight road running north-south through the clock tower, which is called the "North-South Avenue". This corresponds to the $ y $-axis on a 2D coordinate plane.
• Additionally, there are infinitely many roads parallel to the North-South Avenue, spaced 1 unit apart. These correspond to the lines $x = (integer \neq 0)$.

New AtCoder City has $ N $ villages. The $ i $-th village is located at the intersection $ (X_i, Y_i) $ and has a population of $ P_i $. Each citizen lives in one of these villages.

Currently, there are only two railway lines: one running infinitely along the East-West Avenue and the other running infinitely along the North-South Avenue.
The mayor, M-kun, thinks this is inconvenient for commuting, so he decided to build $ K $ new railway lines, each running infinitely along selected roads.

Here, the "walking distance" for each citizen in New AtCoder City is defined as the distance from their village to the nearest railway line.
The goal is to build the railway lines such that the total walking distance $ S $ of all citizens is minimized.

For each $K = 0, 1, 2, \ldots, N$, what is the minimum value of $ S $ after building the railway lines?

Input Format

The input is given from the standard input in the following format:

$ N $ $ X_1 $ $ Y_1 $ $ P_1 $ $ X_2 $ $ Y_2 $ $ P_2 $ $ : $ $ : $ $ : $ $ X_N $ $ Y_N $ $ P_N $

Output Format

Output the answer in $ N+1 $ lines.
The $ i $-th line $(i = 1, \ldots, N+1)$ should contain the minimum value of $ S $ after building the railway lines for the case $ K = i - 1 $ as an integer.

Sample Input and Output

Sample Input #1

3
1 2 300
3 3 600
1 4 800

Sample Output #1

2900
900
0
0

Sample Input #2

5
3 5 400
5 3 700
5 5 1000
5 7 700
7 5 400

Sample Output #2

13800
1600
0
0
0
0

Sample Input #3

6
2 5 1000
5 2 1100
5 5 1700
-2 -5 900
-5 -2 600
-5 -5 2200

Sample Output #3

26700
13900
3200
1200
0
0
0

Sample Input #4

8
2 2 286017
3 1 262355
2 -2 213815
1 -3 224435
-2 -2 136860
-3 -1 239338
-2 2 217647
-1 3 141903

Sample Output #4

2576709
1569381
868031
605676
366338
141903
0
0
0

Notes/Hints

Constraints

• $1 \leq N \leq 15$
• $-10,000 \leq X_i \leq 10,000$
• $-10,000 \leq Y_i \leq 10,000$
• $1 \leq P_i \leq 1,000,000$
• The locations $ (X_i, Y_i) $ of the $ N $ villages are all distinct.
• All inputs are integers.

Sample Explanation 1

For $ K = 0 $, the residents of villages 1, 2, and 3 need to walk distances of 1, 3, and 1 respectively to reach the railway lines. Therefore, the total walking distance $ S $ is $1 \times 300 + 3 \times 600 + 1 \times 800 = 2900$. For $ K = 1 $, if a railway line is built 4 units north of the East-West Avenue, the walking distances for the residents of villages 1, 2, and 3 become 1, 1, and 0 respectively. Then, $S = 1 \times 300 + 1 \times 600 + 0 \times 800 = 900$. Many other construction sites are possible, but none can reduce $ S $ to less than 900. For $ K = 2 $, if railway lines are built 1 and 3 units east of the North-South Avenue, all residents of New AtCoder City can reach the railway lines with a walking distance of 0, so $ S = 0 $. Also, for $ K = 3 $, $ S = 0 $ can be achieved. The optimal construction methods for the cases of $ K = 0, 1, 2 $ are shown in the figure below. The roads painted blue represent the railway lines.

Sample Explanation 2

The optimal construction methods for the cases of $ K = 1, 2 $ are shown in the figure below.

Sample Explanation 3

The optimal construction method for the case of $ K = 3 $ is shown in the figure below.

Sample Explanation 4

The optimal construction method for the case of $ K = 4 $ is shown in the figure below.

见题面 Input 部分

见题面 Output 部分