Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official.
×

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

C. Optimal Polygon Perimeter

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputYou 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, \ldots, p_k$$$ $$$(k \geq 3)$$$, then the perimeter of the polygon is $$$d(p_1, p_2) + d(p_2, p_3) + \ldots + 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:

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), \ldots, 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 \leq n \leq 3\cdot 10^5$$$) — the number of points.

Each of the next $$$n$$$ lines contains two integers $$$x_i$$$ and $$$y_i$$$ ($$$-10^8 \leq x_i, y_i \leq 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\leq i\leq 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$$$.

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/12/2018 00:32:32 (f2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|