Problem: New AtCoder City has an infinite grid of streets, as follows:

* At the center of the city stands a clock tower. Let (0, 0) be the coordinates of this point.
* A straight street, which we will call East-West Main Street, runs east-west and passes the clock tower. It corresponds to the x-axis in the two-dimensional coordinate plane.
* There are also other infinitely many streets parallel to East-West Main Street, with a distance of 1 between them. They correspond to the lines \ldots, y = -2, y = -1, y = 1, y = 2, \ldots in the two-dimensional coordinate plane.
* A straight street, which we will call North-South Main Street, runs north-south and passes the clock tower. It corresponds to the y-axis in the two-dimensional coordinate plane.
* There are also other infinitely many streets parallel to North-South Main Street, with a distance of 1 between them. They correspond to the lines \ldots, x = -2, x = -1, x = 1, x = 2, \ldots in the two-dimensional coordinate plane.



There are N residential areas in New AtCoder City. The i-th area is located at the intersection with the coordinates (X_i, Y_i) and has a population of P_i. Each citizen in the city lives in one of these areas.

The city currently has only two railroads, stretching infinitely, one along East-West Main Street and the other along North-South Main Street.
M-kun, the mayor, thinks that they are not enough for the commuters, so he decides to choose K streets and build a railroad stretching infinitely along each of those streets.

Let the walking distance of each citizen be the distance from his/her residential area to the nearest railroad.
M-kun wants to build railroads so that the sum of the walking distances of all citizens, S, is minimized.

For each K = 0, 1, 2, \dots, N, what is the minimum possible value of S after building railroads?

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 of the N residential areas, (X_i, Y_i), are all distinct.
* All values in input are integers.

Input

Input is given from 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

Print the answer in N+1 lines.
The i-th line (i = 1, \ldots, N+1) should contain the minimum possible value of S after building railroads for the case K = i-1.

Examples

Input

3
1 2 300
3 3 600
1 4 800


Output

2900
900
0
0


Input

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


Output

13800
1600
0
0
0
0


Input

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


Output

26700
13900
3200
1200
0
0
0


Input

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


Output

2576709
1569381
868031
605676
366338
141903
0
0
0

Solution (in JAVA):

Solution:
import java.util.*;

public class Main {

    static class Node {
        long x, y, val;
        Node() {}
        Node(long x, long y, long val) {
            this.x = x;
            this.y = y;
            this.val = val;
        }
    }
    private static long[][] dp;
    private static int n;
    private static Map<Integer, Long> M;
    private static int total;

    private static long process(Node[] arr, int s) {
        if (M.containsKey(s)) return M.get(s);
        List<Node> list = new ArrayList();
        long ans = Long.MAX_VALUE;
        long sum = 0L;
        for (int j = 0; j < n; j++) if ((s & (1 << j)) > 0) {
            list.add(arr[j]);
            sum += arr[j].val;
        }
        if (list.size() <= 1) return 0L;

        Collections.sort(list, (a, b) -> (int) (a.x - b.x));
        int pos = 0;
        long cnt = list.get(0).val;
        while (cnt < (sum + 1) / 2) {
            pos++;
            cnt += list.get(pos).val;
        }
        long x = 0;
        if (sum % 2 == 0 && cnt == sum / 2) {
            x = (list.get(pos).x + list.get(pos + 1).x) / 2;
        } else {
            x = list.get(pos).x;
        }
        long cal = 0;
        for (int i = 0; i < list.size(); i++) cal += Math.abs(x - list.get(i).x) * list.get(i).val;
        ans = Math.min(ans, cal);


        Collections.sort(list, (a, b) -> (int) (a.y - b.y));
        pos = 0;
        cnt = list.get(0).val;
        while (cnt < (sum + 1) / 2) {
            pos++;
            cnt += list.get(pos).val;
        }
        long y = 0;
        if (sum % 2 == 0 && cnt == sum / 2) {
            y = (list.get(pos).y + list.get(pos + 1).y) / 2;
        } else {
            y = list.get(pos).y;
        }
        cal = 0;
        for (int i = 0; i < list.size(); i++) cal += Math.abs(y - list.get(i).y) * list.get(i).val;
        ans = Math.min(ans, cal);

        M.put(s, ans);
        return ans;
    }

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        Node[] a = new Node[n];
        M = new HashMap<>();
        for (int i = 0; i < n; i++) {
            long x = scan.nextLong();
            long y = scan.nextLong();
            long val = scan.nextLong();
            a[i] = new Node(x, y, val);
        }
        total = 1 << n;
        dp = new long[n + 1][total];
        for (int s = 1; s < total; s++) {
            long cnt = 0;
            for (int j = 0; j < n; j++) if ((s & (1 << j)) > 0) {
                cnt += Math.min(Math.abs(a[j].x), Math.abs(a[j].y)) * a[j].val;
            }
            dp[0][s] = cnt;
        }
        for (int i = 1; i <= n; i++) {
            for (int s = 1; s < total; s++) {
                if (dp[i - 1][s] == 0) {
                    dp[i][s] = 0;
                    continue;
                }
                long cnt = Long.MAX_VALUE;
                for (int s1 = s; s1 != 0; s1 = (s1 - 1) & s) {
                    int s2 = s ^ s1;
                    if (dp[i - 1][s2] > cnt) continue;
                    cnt = Math.min(cnt, dp[i - 1][s2] + process(a, s1));
                }
                dp[i][s] = cnt;
            }
            if (dp[i][total - 1] == 0) break;
        }
        for (int i = 0; i <= n; i++) System.out.println(dp[i][total - 1]);
    }
}