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, \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:

 [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), \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$.

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = "import sys\ninput = sys.stdin.readline\n\nn = int(input())\nx = []\ny = []\nfor i in range(n):\n    xi, yi = map(int, input().split())\n    x.append(xi)\n    y.append(yi)\nmin_x = min(x)\nmax_x = max(x)\nmin_y = min(y)\nmax_y = max(y)\nanswer = 0\nfor i in range(n):\n    dx = max(max_x - x[i], x[i] - min_x)\n    dy = max(max_y - y[i], y[i] - min_y)\n    answer = max(answer, dx + dy)\nprint(2*answer, end = ' ')\nfor i in range(4, n + 1):\n    print(2*(max_x - min_x + max_y - min_y), end = ' ')"
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 13455