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.
#include <bits/stdc++.h>
using namespace std;
const int N = 100100;
const int M = 200010;
const long long inf = 1e15;
const int mod = 1000000007;
long long qpow(long long a, long long b) {
  long long ans = 1;
  while (b) {
    if (b & 1) ans = ans * a % mod;
    a = a * a % mod;
    b /= 2;
  }
  return ans;
}
long long qpow(long long a, long long b, long long c) {
  long long ans = 1;
  while (b) {
    if (b & 1) ans = ans * a % c;
    a = a * a % c;
    b /= 2;
  }
  return ans;
}
const double eps = 1e-10, pi = acos(-1);
int dcmp(double x) {
  if (fabs(x) < eps)
    return 0;
  else
    return x < 0 ? -1 : 1;
}
struct Point {
  double x, y;
  Point(double x = 0, double y = 0) : x(x), y(y) {}
  void read() { scanf("%lf%lf", &x, &y); }
  void print() { printf("%f %f\n", x, y); }
  bool operator<(const Point &rhs) const {
    return dcmp(x - rhs.x) < 0 || (dcmp(x - rhs.x) == 0 && y < rhs.y);
  }
  bool operator==(const Point &rhs) const {
    return dcmp(x - rhs.x) == 0 && dcmp(y - rhs.y) == 0;
  }
};
struct Circle {
  Point c;
  double r;
  Circle(Point c = Point(0, 0), double r = 0) : c(c), r(r) {}
  Point getPoint(double rad) {
    return Point(cos(rad) * r + c.x, sin(rad) * r + c.y);
  }
};
Point operator+(Point A, Point B) { return Point(A.x + B.x, A.y + B.y); }
Point operator-(Point A, Point B) { return Point(A.x - B.x, A.y - B.y); }
Point operator*(Point A, double p) { return Point(A.x * p, A.y * p); }
Point operator/(Point A, double p) { return Point(A.x / p, A.y / p); }
double Dot(Point A, Point B) { return A.x * B.x + A.y * B.y; }
double Length(Point A) { return sqrt(Dot(A, A)); }
double Angle(Point A, Point B) {
  double b = A.x * A.x + A.y * A.y, c = B.x * B.x + B.y * B.y,
         a = (A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y);
  double d = 2.0 * sqrt(b) * sqrt(c);
  return acos((b + c - a) / d);
}
double Cross(Point A, Point B) { return A.x * B.y - A.y * B.x; }
Point Rotate(Point A, double rad) {
  return Point(A.x * cos(rad) - A.y * sin(rad),
               A.x * sin(rad) + A.y * cos(rad));
}
double dist(Point a, Point b) {
  return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
double RadToDegree(double rad) { return rad / pi * 180; }
double DegreeToRad(double deg) { return deg / 180 * pi; }
struct Line {
  Point a, b;
  Line(Point x = Point(0, 0), Point y = Point(0, 0)) : a(x), b(y) {}
  Line(Point p, double ang) {
    a = p;
    if (dcmp(ang - pi / 2) == 0)
      b = a + Point(0, 1);
    else
      b = a + Point(1, tan(ang));
  }
  Line(double x, double y, double z) {
    if (dcmp(x) == 0) {
      a = Point(0, -z / y);
      b = Point(1, -z / y);
    } else if (dcmp(y) == 0) {
      a = Point(-z / x, 0);
      b = Point(-z / x, 1);
    } else {
      a = Point(0, -z / y);
      b = Point(1, (-z - x) / y);
    }
  }
  bool operator<(const Line &rhs) const {
    double x = atan2(b.y - a.y, b.x - a.x),
           y = atan2(rhs.b.y - rhs.a.y, rhs.b.x - rhs.a.x);
    if (dcmp(x - y) == 0) return dcmp(Cross(rhs.b - rhs.a, a - rhs.a)) > 0;
    return dcmp(x - y) < 0;
  }
  void read() { scanf("%lf%lf%lf%lf", &a.x, &a.y, &b.x, &b.y); }
  void print() { printf("%f %f %f %f\n", a.x, a.y, b.x, b.y); }
};
Line translation(Line p, double y) {
  Point x = p.b - p.a;
  x = Rotate(x, pi / 2);
  x = x / Length(x);
  x = x * y;
  p.a = p.a + x;
  p.b = p.b + x;
  return p;
}
bool IsOnPointToSegment(const Point &p, const Point &a1, const Point &a2) {
  if (dcmp(Cross(a1 - p, a2 - p)))
    return false;
  else if (dcmp(p.x - min(a1.x, a2.x)) >= 0 &&
           dcmp(p.x - max(a1.x, a2.x)) <= 0 &&
           dcmp(p.y - min(a1.y, a2.y)) >= 0 && dcmp(p.y - max(a1.y, a2.y)) <= 0)
    return true;
  else
    return false;
}
double GetDistancePointToLine(Point p, Line x) {
  Point a = x.a, b = x.b;
  Point v1 = b - a, v2 = p - a;
  return fabs(Cross(v1, v2)) / Length(v1);
}
double GetDistancePointToSegment(Point p, Line x) {
  if (x.a == x.b) return Length(p - x.a);
  Point v1 = x.b - x.a, v2 = p - x.a, v3 = p - x.b;
  if (dcmp(Dot(v1, v2)) < 0)
    return Length(v2);
  else if (dcmp(Dot(v1, v3)) > 0)
    return Length(v3);
  else
    return fabs(Cross(v1, v2)) / Length(v1);
}
Point GetProjectionPointToLine(Point p, Line x) {
  Point v = x.b - x.a;
  return x.a + v * (Dot(v, p - x.a) / Dot(v, v));
}
Point GetReflectionPointToLine(Point p, Line x) {
  Point y = GetProjectionPointToLine(p, x);
  return p + (y - p) * 2.0;
}
bool IsParallelLineToLine(Line x, Line y) {
  Point a = x.a - x.b, b = y.a - y.b;
  if (dcmp(Cross(a, b)) == 0) return true;
  return false;
}
bool IsOrthogonalLineToLine(Line x, Line y) {
  Point a = x.a - x.b, b = y.a - y.b;
  double w = Dot(a, b);
  if (dcmp(w) == 0) return true;
  return false;
}
bool IsIntersectionSegmentToSegment1(Line x, Line y) {
  Point a = x.a, b = x.b, c = y.a, d = y.b;
  double a1 = Cross(b - a, d - a), a2 = Cross(c - a, b - a),
         a3 = Cross(d - c, a - c), a4 = Cross(b - c, d - c);
  return dcmp(a1) * dcmp(a2) >= 0 && dcmp(a3) * dcmp(a4) >= 0 &&
         max(c.x, d.x) >= min(a.x, b.x) && max(a.x, b.x) >= min(c.x, d.x) &&
         max(c.y, d.y) >= min(a.y, b.y) && max(a.y, b.y) >= min(c.y, d.y);
}
bool IsIntersectionSegmentToSegment2(Line x, Line y) {
  Point a = x.a, b = x.b, c = y.a, d = y.b;
  double a1 = Cross(b - a, d - a), a2 = Cross(c - a, b - a),
         a3 = Cross(d - c, a - c), a4 = Cross(b - c, d - c);
  return dcmp(a1) * dcmp(a2) > 0 && dcmp(a3) * dcmp(a4) > 0;
}
bool IsIntersectionSegmentToLine(Line x, Line y) {
  if (dcmp(Cross(x.a - y.b, y.a - y.b)) * dcmp(Cross(y.a - y.b, x.b - y.b)) >=
      0)
    return true;
  return false;
}
Point GetIntersectionLineToLine(Line x, Line y) {
  Point a = x.a, b = x.b - x.a;
  Point c = y.a, d = y.b - y.a;
  Point u = a - c;
  double t = Cross(d, u) / Cross(b, d);
  return a + b * t;
}
double GetDistanceSegmentToSegment(Line x, Line y) {
  if (IsIntersectionSegmentToSegment1(x, y)) return 0;
  double v1 =
      min(GetDistancePointToLine(x.a, y), GetDistancePointToLine(x.b, y));
  double v2 =
      min(GetDistancePointToLine(y.a, x), GetDistancePointToLine(y.b, x));
  return min(v1, v2);
}
double GetAreaPolygon(vector<Point> &p) {
  int n = p.size();
  double area = 0;
  for (int i = 1; i < n - 1; i++) area += Cross(p[i] - p[0], p[i + 1] - p[0]);
  return fabs(area / 2);
}
double GetPerimeterPolygon(vector<Point> &p) {
  if (p.size() == 0 || p.size() == 1) return 0;
  double ret = dist(p[0], p[p.size() - 1]);
  for (int i = 0; i < p.size() - 1; i++) ret += dist(p[i + 1], p[i]);
  return ret;
}
int IsInPointToPolygon(Point p, vector<Point> &poly) {
  int wn = 0, n = poly.size();
  for (int i = 0; i < n; i++) {
    if (IsOnPointToSegment(p, poly[i], poly[(i + 1) % n])) return -1;
    int k = dcmp(Cross(poly[(i + 1) % n] - poly[i], p - poly[i]));
    int d1 = dcmp(poly[i].y - p.y);
    int d2 = dcmp(poly[(i + 1) % n].y - p.y);
    if (k > 0 && d1 <= 0 && d2 > 0) wn++;
    if (k < 0 && d2 <= 0 && d1 > 0) wn--;
  }
  if (wn != 0) return 1;
  return 0;
}
int IsInSegmentToPolygon(vector<Point> &poly, Line x) {
  for (int i = 1; i < ((int)poly.size()); i++) {
    if (IsIntersectionSegmentToSegment1(Line(poly[i], poly[i - 1]), x)) {
      return -1;
    }
  }
  if (((int)poly.size()) > 1)
    if (IsIntersectionSegmentToSegment1(Line(poly[0], poly[poly.size() - 1]),
                                        x))
      return -1;
  if (IsInPointToPolygon(x.a, poly) == 1) return 1;
  return 0;
}
bool IsConvexPolygon(vector<Point> &p) {
  int n = p.size();
  if (dcmp(Cross(p[0] - p[n - 1], p[1] - p[0])) *
          dcmp(Cross(p[n - 1] - p[n - 2], p[0] - p[n - 1])) <
      0)
    return false;
  for (int i = 2; i < n - 1; i++)
    if (dcmp(Cross(p[i] - p[i - 1], p[i + 1] - p[i])) *
            dcmp(Cross(p[i - 1] - p[i - 2], p[i] - p[i - 1])) <
        0)
      return false;
  return true;
}
void GetRectanglePoint(Point a, Point b, Point &c, Point &d) {
  c.x = (a.x + b.x + b.y - a.y) / 2;
  c.y = (a.y + b.y + a.x - b.x) / 2;
  d.x = (a.x + b.x - b.y + a.y) / 2;
  d.y = (a.y + b.y - a.x + b.x) / 2;
}
bool IsIntersectionPolygonToPolygon(vector<Point> &a, vector<Point> &b) {
  int n = a.size(), m = b.size();
  for (int i = 0; i < n; i++) {
    Line x;
    x.a = a[i];
    x.b = a[(i + 1) % n];
    for (int j = 0; j < m; j++) {
      Line y;
      y.a = b[j];
      y.b = b[(j + 1) % m];
      if (IsIntersectionSegmentToSegment1(x, y)) return true;
    }
  }
  return false;
}
void GetConvexPolygon(vector<Point> p, vector<Point> &ch) {
  int n = p.size(), m = 0;
  sort(p.begin(), p.end());
  for (int i = 0; i < n; i++) {
    while (m > 1 && dcmp(Cross(ch[m - 1] - ch[m - 2], p[i] - ch[m - 2])) < 0)
      ch.pop_back(), m--;
    ch.push_back(p[i]);
    m++;
  }
  int k = m;
  for (int i = n - 2; i >= 0; i--) {
    while (m > k && dcmp(Cross(ch[m - 1] - ch[m - 2], p[i] - ch[m - 2])) < 0)
      ch.pop_back(), m--;
    ch.push_back(p[i]);
    m++;
  }
  if (n > 1) ch.pop_back(), m--;
}
double GetDiameterConvex(vector<Point> &p) {
  if (((int)p.size()) == 1) return 0;
  if (((int)p.size()) == 2) return Length(p[1] - p[0]);
  double ret = 0;
  for (int i = 0, x = 0; i < ((int)p.size()); i++) {
    while (Cross(p[i] - p[i + 1], p[i + 1] - p[(x + 1) % ((int)p.size())]) >=
           Cross(p[i] - p[i + 1], p[i + 1] - p[x]))
      x = (x + 1) % ((int)p.size());
    ret = max(ret, max(Length(p[x] - p[i]), Length(p[x] - p[i + 1])));
  }
  return ret;
}
void GetConVexHalfplane(vector<Line> &v, vector<Point> &ret) {
  sort((v).begin(), (v).end());
  int l = 0, r = 0, n = v.size();
  Point t[N];
  Line q[N];
  for (int i = 0; i < n; ++i) {
    if (i && dcmp(atan2(v[i].b.y - v[i].a.y, v[i].b.x - v[i].a.x) -
                  atan2(v[i - 1].b.y - v[i - 1].a.y,
                        v[i - 1].b.x - v[i - 1].a.x)) == 0)
      continue;
    while (r - l > 1 && dcmp(Cross(v[i].a - v[i].b, t[r] - v[i].b)) > 0) --r;
    while (r - l > 1 && dcmp(Cross(v[i].a - v[i].b, t[l + 2] - v[i].b)) > 0)
      ++l;
    q[++r] = v[i];
    if (r - l > 1) t[r] = GetIntersectionLineToLine(q[r], q[r - 1]);
  }
  while (r - l > 1 &&
         dcmp(Cross(q[l + 1].a - q[l + 1].b, t[r] - q[l + 1].b)) > 0)
    --r;
  t[r + 1] = GetIntersectionLineToLine(q[l + 1], q[r]);
  ++r;
  for (int i = l + 2; i <= r; i++) ret.push_back(t[i]);
}
double GetAreaCircle(Circle a) { return pi * a.r * a.r; }
Point GetCircleCenter(Point A, Point B, Point C) {
  Point o;
  double a1 = B.x - A.x, b1 = B.y - A.y, c1 = (a1 * a1 + b1 * b1) / 2;
  double a2 = C.x - A.x, b2 = C.y - A.y, c2 = (a2 * a2 + b2 * b2) / 2;
  double d = a1 * b2 - a2 * b1;
  o.x = A.x + (c1 * b2 - c2 * b1) / d;
  o.y = A.y + (a1 * c2 - a2 * c1) / d;
  return o;
}
int IsIntersectionCircleToCircle(Circle a, Circle b) {
  double d = dist(a.c, b.c);
  if (dcmp(d - a.r - b.r) > 0) return 0;
  if (dcmp(d - a.r - b.r) == 0) return 1;
  if (dcmp(d + min(a.r, b.r) - max(a.r, b.r)) == 0) return 2;
  if (dcmp(d + min(a.r, b.r) - max(a.r, b.r)) > 0) return 4;
  return 3;
}
int IsIntersectionSegmentToCircle(Line a, Circle b) {
  double len1 = GetDistancePointToSegment(b.c, a);
  double len2 = max(dist(a.a, b.c), dist(a.b, b.c));
  if (dcmp(len1 - b.r) <= 0 && dcmp(len2 - b.r) >= 0) return 1;
  if (dcmp(len1 - b.r) < 0 && dcmp(len2 - b.r) < 0) return -1;
  if (dcmp(len1 - b.r) > 0 && dcmp(len2 - b.r) > 0) return -2;
}
double GetAreaCircleToCircle(Circle a, Circle b) {
  int x = IsIntersectionCircleToCircle(a, b);
  if (x == 0 || x == 1) return 0;
  if (x == 3 || x == 2) return min(GetAreaCircle(a), GetAreaCircle(b));
  double d = dist(a.c, b.c);
  if (dcmp(a.r - b.r) > 0) swap(a, b);
  double ang1 = acos((a.r * a.r + d * d - b.r * b.r) / (2.0 * a.r * d));
  double ang2 = acos((b.r * b.r + d * d - a.r * a.r) / (2.0 * b.r * d));
  return ang1 * a.r * a.r + ang2 * b.r * b.r - a.r * d * sin(ang1);
}
int GetIntersectionCircleToCircle(Circle a, Circle b, Point &p1, Point &p2) {
  if (a.r > b.r) swap(a, b);
  double r = a.r, R = b.r, d = Length(a.c - b.c);
  if (dcmp(d) == 0 && a.c == b.c) return 0;
  if (R > d + r || d > R + r) return 0;
  double cos_ang = (r * r + d * d - R * R) / (2.0 * r * d);
  double sin_ang = sqrt(1.0 - cos_ang * cos_ang);
  Point o = (b.c - a.c) * (1.0 / d);
  o = a.c + o * (r * cos_ang);
  Point pt = Point(a.c.y - b.c.y, b.c.x - a.c.x) * (1.0 / d);
  p1 = o + pt * (r * sin_ang);
  p2 = o - pt * (r * sin_ang);
  if (dcmp(p1.x - p2.x) == 0 && dcmp(p1.y - p2.y) == 0) return 1;
  return 2;
}
bool IsInCircleToPolygon(vector<Point> &v, Circle a) {
  for (int i = 0; i < ((int)v.size()); i++) {
    Line t;
    t.a = v[i];
    t.b = v[(i + 1) % ((int)v.size())];
    if (IsIntersectionSegmentToCircle(t, a) != -2) return false;
  }
  if (IsInPointToPolygon(a.c, v)) return true;
  return false;
}
double GetCircleConvex(vector<int> v) {
  int n = v.size();
  double l = 0, r = 10000;
  for (int i = 0; i < 30; i++) {
    double m = (l + r) / 2.0;
    vector<Line> tp;
    for (int j = 0; j < n; j++) tp.push_back(Line(v[j], v[(j + 1) % n]));
    for (int j = 0; j < n; j++) tp[j] = translation(tp[j], m);
    vector<Point> c;
    GetConVexHalfplane(tp, c);
    if (((int)c.size()) < 3)
      r = m;
    else
      l = m;
  }
  return r;
  vector<Line> tp;
  for (int i = 0; i < n; i++) tp.push_back(Line(v[i], v[(i + 1) % n]));
  for (int i = 0; i < n; i++) tp[i] = translation(tp[i], r);
  vector<Point> c;
  GetConVexHalfplane(tp, c);
}
void MinPointCoverByCircle(Point *p, int n, Point &o, double &r) {
  random_shuffle(p, p + n);
  o = p[0], r = 0;
  for (int i = 1; i < n; i++) {
    if (dist(p[i], o) > r + eps) {
      o = p[i];
      r = 0;
      for (int j = 0; j < i; j++) {
        if (dist(p[j], o) > r + eps) {
          o.x = (p[i].x + p[j].x) / 2;
          o.y = (p[i].y + p[j].y) / 2;
          r = dist(p[j], o);
          for (int k = 0; k < j; k++) {
            if (dist(p[k], o) > r + eps) {
              o = GetCircleCenter(p[i], p[j], p[k]);
              r = dist(p[i], o);
            }
          }
        }
      }
    }
  }
}
vector<pair<int, int> > v;
int n;
int main() {
  scanf("%d", &n);
  for (int i = 0; i < n; i++) {
    pair<int, int> x;
    scanf("%d%d", &x.first, &x.second);
    v.push_back(x);
  }
  int minx = v[0].first, miny = v[0].second, maxx = v[0].first,
      maxy = v[0].second;
  for (int i = 1; i < n; i++) {
    minx = min(minx, v[i].first);
    miny = min(miny, v[i].second);
    maxx = max(maxx, v[i].first);
    maxy = max(maxy, v[i].second);
  }
  int ans = 0;
  for (int i = 0; i < n; i++) {
    int dx = max(v[i].first - minx, maxx - v[i].first);
    int dy = max(v[i].second - miny, maxy - v[i].second);
    ans = max(ans, 2 * (dx + dy));
  }
  printf("%d", ans);
  for (int i = 4; i <= n; i++) printf(" %d", 2 * (maxx - minx + maxy - miny));
}
