1044_C. Optimal Polygon Perimeter_28525
You are given n points on the plane. The polygon formed from all the n points is strictly convex, that is, the polygon is convex, and there are no three collinear points (i.e. lying in the same straight line). The points are numbered from 1 to n, in clockwise order.

We define the distance between two points p_1 = (x_1, y_1) and p_2 = (x_2, y_2) as their Manhattan distance: $$$d(p_1, p_2) = |x_1 - x_2| + |y_1 - y_2|.$$$

Furthermore, we define the perimeter of a polygon, as the sum of Manhattan distances between all adjacent pairs of points on it; if the points on the polygon are ordered as p_1, p_2, …, p_k (k ≥ 3), then the perimeter of the polygon is d(p_1, p_2) + d(p_2, p_3) + … + d(p_k, p_1).

For some parameter k, let's consider all the polygons that can be formed from the given set of points, having any k vertices, such that the polygon is not self-intersecting. For each such polygon, let's consider its perimeter. Over all such perimeters, we define f(k) to be the maximal perimeter.

Please note, when checking whether a polygon is self-intersecting, that the edges of a polygon are still drawn as straight lines. For instance, in the following pictures:

<image>

In the middle polygon, the order of points (p_1, p_3, p_2, p_4) is not valid, since it is a self-intersecting polygon. The right polygon (whose edges resemble the Manhattan distance) has the same order and is not self-intersecting, but we consider edges as straight lines. The correct way to draw this polygon is (p_1, p_2, p_3, p_4), which is the left polygon.

Your task is to compute f(3), f(4), …, f(n). In other words, find the maximum possible perimeter for each possible number of points (i.e. 3 to n).

Input

The first line contains a single integer n (3 ≤ n ≤ 3⋅ 10^5) — the number of points. 

Each of the next n lines contains two integers x_i and y_i (-10^8 ≤ x_i, y_i ≤ 10^8) — the coordinates of point p_i.

The set of points is guaranteed to be convex, all points are distinct, the points are ordered in clockwise order, and there will be no three collinear points.

Output

For each i (3≤ i≤ n), output f(i).

Examples

Input

4
2 4
4 3
3 0
1 3


Output

12 14 

Input

3
0 0
0 2
2 0


Output

8 

Note

In the first example, for f(3), we consider four possible polygons: 

  * (p_1, p_2, p_3), with perimeter 12. 
  * (p_1, p_2, p_4), with perimeter 8. 
  * (p_1, p_3, p_4), with perimeter 12. 
  * (p_2, p_3, p_4), with perimeter 12. 



For f(4), there is only one option, taking all the given points. Its perimeter 14.

In the second example, there is only one possible polygon. Its perimeter is 8.
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author Vadim
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        FastScanner in = new FastScanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskE solver = new TaskE();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskE {
        public void solve(int testNumber, FastScanner in, PrintWriter out) {
            int n = in.ni();
            Point[] p = new Point[n];
            int MAX = 1000000000;
            int minX = MAX, minY = MAX, maxX = -MAX, maxY = -MAX;
            for (int i = 0; i < n; i++) {
                p[i] = new Point(in.ni(), in.ni());
                minX = Math.min(minX, p[i].x);
                maxX = Math.max(maxX, p[i].x);
                minY = Math.min(minY, p[i].y);
                maxY = Math.max(maxY, p[i].y);
            }
            int ans4 = 2 * (maxX - minX) + 2 * (maxY - minY);
            int ans3 = 0;
            for (int i = 0; i < n; i++) {
                int per = p[i].x - minX + p[i].y - minY;
                ans3 = Math.max(ans3, per);
                per = maxX - p[i].x + p[i].y - minY;
                ans3 = Math.max(ans3, per);
                per = maxX - p[i].x + maxY - p[i].y;
                ans3 = Math.max(ans3, per);
                per = p[i].x - minX + maxY - p[i].y;
                ans3 = Math.max(ans3, per);
            }
            out.print((2 * ans3) + " ");
            for (int i = 4; i <= n; i++) {
                out.print(ans4 + " ");
            }
            out.println();

        }

        class Point {
            int x;
            int y;

            public Point(int x, int y) {
                this.x = x;
                this.y = y;
            }

        }

    }

    static class FastScanner {
        private BufferedReader in;
        private StringTokenizer st;

        public FastScanner(InputStream stream) {
            in = new BufferedReader(new InputStreamReader(stream));
        }

        public String ns() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    String rl = in.readLine();
                    if (rl == null) {
                        return null;
                    }
                    st = new StringTokenizer(rl);
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return st.nextToken();
        }

        public int ni() {
            return Integer.parseInt(ns());
        }

    }
}


4
2 4
4 3
3 0
1 3
 3
0 0
0 2
2 0
 12
-83240790 -33942371
-83240805 -33942145
-83240821 -33941752
-83240424 -33941833
-83240107 -33942105
-83239958 -33942314
-83239777 -33942699
-83239762 -33942925
-83239746 -33943318
-83240143 -33943237
-83240460 -33942965
-83240609 -33942756
 3
51800836 -5590860
51801759 -5590419
51801320 -5590821
 8
0 3
2 2
3 0
2 -2
0 -3
-2 -2
-3 0
-2 2
 20
-2967010 48581504
-2967318 48581765
-2967443 48581988
-2967541 48582265
-2967443 48582542
-2967318 48582765
-2967010 48583026
-2966691 48583154
-2966252 48583234
-2965813 48583154
-2965494 48583026
-2965186 48582765
-2965061 48582542
-2964963 48582265
-2965061 48581988
-2965186 48581765
-2965494 48581504
-2965813 48581376
-2966252 48581296
-2966691 48581376
 4
-100000000 -100000000
-100000000 100000000
100000000 100000000
100000000 -100000000
 3
77445196 95326351
77444301 95326820
77444705 95326693
 4
0 99999999
0 100000000
1 -99999999
1 -100000000
 4
100000000 0
0 -100000000
-100000000 0
0 100000000
 4
0 0
10 10
10 9
1 0
 3
97972354 -510322
97972814 -510361
97972410 -510528
 4
12345678 99999999
12345679 100000000
12345680 99999999
12345679 99999998
 4
-95989415 -89468419
-95989014 -89468179
-95989487 -89468626
-95989888 -89468866
 6
-1000 1000
-998 1001
-996 1000
-996 996
-997 995
-1001 997
 10
811055 21220458
813063 21222323
815154 21220369
817067 21218367
815214 21216534
813198 21214685
803185 21212343
805063 21214436
806971 21216475
808966 21218448
 3
-99297393 80400183
-99297475 80399631
-99297428 80399972
 12
-83240790 -33942371
-83240805 -33942145
-83240821 -33941752
-83240424 -33941833
-83240107 -33942105
-83239958 -33942314
-83239777 -33942699
-83239762 -33942925
-83239746 -33943318
-66971704 -33943237
-83240460 -33942965
-83240609 -33942756
 3
51800836 -1756836
51801759 -5590419
51801320 -5590821
 8
0 3
2 2
3 0
2 -2
0 -3
-2 -2
-3 1
-2 2
 4
-100000000 -100000000
-100000000 100000000
100000000 101000000
100000000 -100000000
 3
77445196 171582774
77444301 95326820
77444705 95326693
 4
0 111328374
0 100000000
1 -99999999
1 -100000000
 4
100100000 0
0 -100000000
-100000000 0
0 100000000
 4
0 0
6 10
10 9
1 0
 3
97972354 -510322
97972814 -510361
3428786 -510528
 4
-95989415 -89468419
-95989014 -89468179
-95989487 -89468626
-148841738 -89468866
 10
811055 21220458
813063 21222323
815154 21220369
1558875 21218367
815214 21216534
813198 21214685
803185 21212343
805063 21214436
806971 21216475
808966 21218448
 3
-99297393 80400183
-99297475 80399631
-99297428 54604918
 4
3 4
4 3
3 0
1 3
 3
0 0
-1 2
2 0
 3
51800836 -1756836
51801759 -5590419
4115806 -5590821
 8
0 3
2 2
3 0
2 -2
0 -3
-2 -2
-3 1
-2 3
 3
89662205 171582774
77444301 95326820
77444705 95326693
 4
0 111328374
0 100000000
1 -99999999
1 -73518429
 4
100100000 0
0 -100000000
-100000000 0
0 100000100
 4
0 0
6 10
10 17
1 0
 3
97972354 -510322
97972814 -510361
9107 -510528
 4
-95989415 -89468419
-95989014 -89468179
-95989487 -89468626
-194052636 -89468866
 3
-99297393 80400183
-196853177 80399631
-99297428 54604918
 4
5 4
4 3
3 0
1 3
 3
0 0
-1 1
2 0
 3
51800836 -1756836
51801759 -6116854
4115806 -5590821
 4
-100000000 -100000000
-100000000 101100000
100000000 101000000
100000000 -100000000
 3
89662205 171582774
77444301 174371428
77444705 95326693
 4
100100000 0
0 -165428644
-100000000 0
0 100000100
 4
0 -1
6 10
10 17
1 0
 3
97972354 -510322
97972814 -510361
10937 -510528
 4
-95989415 -89468419
-95989014 -89468179
-33126318 -89468626
-194052636 -89468866
 3
-46733155 80400183
-196853177 80399631
-99297428 54604918
 4
9 4
4 3
3 0
1 3
 3
0 0
-1 1
4 0
 3
89662205 196980867
77444301 174371428
77444705 95326693
 4
0 111328374
0 100000000
0 -61141526
1 -73518429
 4
100100000 0
0 -165428644
-100000000 0
-1 100000100
 3
97972354 -510322
97972814 -510361
1989 -510528
 3
-64574641 80400183
-196853177 80399631
-99297428 54604918
 3
0 0
-1 1
4 -1
 3
89662205 385501139
77444301 174371428
77444705 95326693
 4
100100000 0
0 -165428644
-100000000 0
-2 100000100
 3
97972354 -510322
11104794 -510361
1989 -510528
 4
-100000000 -100000000
-100000000 101000000
100000000 101000000
100000000 -100000000
 4
0 111328374
0 100000000
0 -99999999
1 -73518429
 3
45955541 -1756836
51801759 -6116854
4115806 -5590821
 4
-100000000 -100000000
-100000000 101100000
000000000 101000000
100000000 -100000000
 4
0 -1
6 5
10 17
1 0
 4
9 4
4 3
4 0
1 3
 3
45955541 -1756836
51801759 -6116854
4115806 -4677823
 4
-100000000 -100000000
-100000000 101100000
000000000 001000000
100000000 -100000000
 4
0 111328374
0 100100000
0 -61141526
1 -73518429
 4
0 -1
6 5
10 17
1 1
 3
-64574641 80400183
-196853177 80399631
-111339133 54604918

12 14
 8
 5282 5282 5282 5282 5282 5282 5282 5282 5282 5282
 2728
 20 24 24 24 24 24
 7648 9032 9032 9032 9032 9032 9032 9032 9032 9032 9032 9032 9032 9032 9032 9032 9032 9032
 800000000 800000000
 2728
 400000002 400000002
 600000000 800000000
 40 40
 1332
 6 8
 3122 3122
 20 22 22 22
 47724 47724 47724 47724 47724 47724 47724 47724
 1268
 32541366 32541366 32541366 32541366 32541366 32541366 32541366 32541366 32541366 32541366 
 7669816 
 20 24 24 24 24 24 
 802000000 802000000 
 152513952 
 422656750 422656750 
 600200000 800200000 
 40 40 
 189088468 
 105706822 105706822 
 1531340 1531340 1531340 1531340 1531340 1531340 1531340 1531340 
 51590694 
 12 14 
 10 
 103039876 
 22 24 24 24 24 24 
 176947970 
 422656748 422656748 
 600200200 800200200 
 54 54 
 195927826 
 196128618 196128618 
 246702098 
 16 16 
 8 
 104091942 
 802200000 802200000 
 182525278 
 731057488 931057488 
 56 56 
 195924166 
 321854010 321854010 
 351830574 
 24 24 
 12 
 227744156 
 369693608 369693608 
 731057490 931057488 
 195942062 
 316147602 
 14 
 604784700 
 731057492 931057488 
 195941142 
 802000000 802000000 
 422656748 422656748 
 104091942 
 802200000 802200000 
 56 56 
 24 24 
 104091942 
 802200000 802200000 
 369693608 369693608 
 56 56 
 316147602 
