Problem: Ksusha is a vigorous mathematician. She is keen on absolutely incredible mathematical riddles. 

Today Ksusha came across a convex polygon of non-zero area. She is now wondering: if she chooses a pair of distinct points uniformly among all integer points (points with integer coordinates) inside or on the border of the polygon and then draws a square with two opposite vertices lying in the chosen points, what will the expectation of this square's area be?

A pair of distinct points is chosen uniformly among all pairs of distinct points, located inside or on the border of the polygon. Pairs of points p, q (p ≠ q) and q, p are considered the same.

Help Ksusha! Count the required expectation.

Input

The first line contains integer n (3 ≤ n ≤ 105) — the number of vertices of Ksusha's convex polygon. Next n lines contain the coordinates of the polygon vertices in clockwise or counterclockwise order. The i-th line contains integers xi, yi (|xi|, |yi| ≤ 106) — the coordinates of the vertex that goes i-th in that order.

Output

Print a single real number — the required expected area. 

The answer will be considered correct if its absolute and relative error doesn't exceed 10 - 6.

Examples

Input

3
0 0
5 5
5 0


Output

4.6666666667


Input

4
-1 3
4 5
6 2
3 -5


Output

8.1583333333


Input

3
17 136
859 937
16 641


Output

66811.3704155169

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
const double eps = 1e-9;
const int N = 110000, M = 2100000, Zero = 1000000;
struct Point {
  int x, y;
} P[N];
int i, j, k, l, m, n, o, p, X[M], Y[M], Lx, Rx, Ly, Ry;
inline int sn(double x) { return x < -eps ? -1 : x > eps ? 1 : 0; }
inline void Init() {
  scanf("%d", &n);
  for (i = 1; i <= n; i++) scanf("%d%d", &P[i].x, &P[i].y);
}
inline double gety(double x, int A, int B) {
  return P[A].y + (x - P[A].x) / (P[B].x - P[A].x) * (P[B].y - P[A].y);
}
inline void SolveX() {
  int x, s, t, U, D, lU, lD;
  s = t = 1;
  double x1, x2, w;
  for (i = 1; i <= n; i++) {
    if (P[i].x < P[s].x) s = i;
    if (P[i].x > P[t].x) t = i;
  }
  U = s + 1;
  if (U > n) U = 1;
  D = s - 1;
  if (!D) D = n;
  lU = lD = s;
  if (P[lU].x == P[U].x) {
    lU = U;
    U++;
    if (U > n) U = 1;
  }
  if (P[lD].x == P[D].x) {
    lD = D;
    D--;
    if (D < 1) D = n;
  }
  for (x = P[s].x; x <= P[t].x; x++) {
    while (P[U].x < x) {
      lU = U;
      U++;
      if (U > n) U = 1;
    }
    while (P[D].x < x) {
      lD = D;
      D--;
      if (D < 1) D = n;
    }
    x1 = gety((double)x, lU, U);
    x2 = gety((double)x, lD, D);
    if (sn(x1 - x2) > 0) {
      w = x1;
      x1 = x2;
      x2 = w;
    }
    x1 = ceil(x1);
    x2 = floor(x2);
    X[x + Zero] = (int)(x2) - (int)(x1) + 1;
  }
  Lx = P[s].x;
  Rx = P[t].x;
}
inline double getx(double y, int A, int B) {
  return P[A].x + (y - P[A].y) / (P[B].y - P[A].y) * (P[B].x - P[A].x);
}
inline void SolveY() {
  int y, s, t, L, R, lL, lR;
  s = t = 1;
  double y1, y2, w;
  for (i = 1; i <= n; i++) {
    if (P[i].y < P[s].y) s = i;
    if (P[i].y > P[t].y) t = i;
  }
  L = s + 1;
  if (L > n) L = 1;
  R = s - 1;
  if (!R) R = n;
  lL = lR = s;
  if (P[lL].y == P[L].y) {
    lL = L;
    L++;
    if (L > n) L = 1;
  }
  if (P[lR].y == P[R].y) {
    lR = R;
    R--;
    if (R < 1) R = n;
  }
  for (y = P[s].y; y <= P[t].y; y++) {
    while (P[L].y < y) {
      lL = L;
      L++;
      if (L > n) L = 1;
    }
    while (P[R].y < y) {
      lR = R;
      R--;
      if (R < 1) R = n;
    }
    y1 = getx((double)y, lL, L);
    y2 = getx((double)y, lR, R);
    if (sn(y1 - y2) > 0) {
      w = y1;
      y1 = y2;
      y2 = w;
    }
    y1 = ceil(y1);
    y2 = floor(y2);
    Y[y + Zero] = (int)(y2) - (int)(y1) + 1;
  }
  Ly = P[s].y;
  Ry = P[t].y;
}
inline double Solve() {
  double ans = 0.0, s0, s1, s2, p, g, x, cul, y;
  s0 = 0.0;
  s1 = 0.0;
  s2 = 0.0;
  for (i = Lx; i <= Rx; i++) {
    g = (double)X[i + Zero];
    x = (double)i;
    cul = x * x * s0 + s2 - 2.0 * x * s1;
    ans += cul * g;
    s0 += g;
    s2 += g * x * x;
    s1 += g * x;
  }
  s0 = 0.0;
  s1 = 0.0;
  s2 = 0.0;
  for (i = Ly; i <= Ry; i++) {
    g = (double)Y[i + Zero];
    y = (double)i;
    cul = y * y * s0 + s2 - 2.0 * y * s1;
    ans += cul * g;
    s0 += g;
    s2 += g * y * y;
    s1 += g * y;
  }
  p = s0 * (s0 - 1.0);
  return ans / p;
}
int main() {
  Init();
  SolveX();
  SolveY();
  printf("%.8lf\n", Solve());
  return 0;
}