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;
int x[100005], y[100005];
int up[2000005], down[2000005];
int A = 1000000;
bool on(int i, int j, int nx, int ny) {
  return 1LL * (x[j] - x[i]) * (ny - y[i]) -
             1LL * (y[j] - y[i]) * (nx - x[i]) ==
         0;
}
bool cw(int i, int j, int nx, int ny) {
  return 1LL * (x[j] - x[i]) * (ny - y[i]) -
             1LL * (y[j] - y[i]) * (nx - x[i]) >=
         0;
}
bool ccw(int i, int j, int nx, int ny) {
  return 1LL * (x[j] - x[i]) * (ny - y[i]) -
             1LL * (y[j] - y[i]) * (nx - x[i]) <=
         0;
}
double solveX(int n) {
  for (int i = -A; i <= A; ++i) {
    up[i + A] = -2 * A;
    down[i + A] = 2 * A;
  }
  bool ok1 = false, ok2 = false;
  for (int i = 2; i < n; ++i)
    if (!on(i - 2, i - 1, x[i], y[i])) {
      ok1 = cw(i - 2, i - 1, x[i], y[i]);
      ok2 = ccw(i - 2, i - 1, x[i], y[i]);
      break;
    }
  for (int i = 0; i < n; ++i) {
    int lx = min(x[i], x[i + 1]), rx = max(x[i], x[i + 1]);
    if (lx == rx) {
      up[lx + A] = max(up[lx + A], max(y[i], y[i + 1]));
      down[lx + A] = min(down[lx + A], min(y[i], y[i + 1]));
    } else
      for (int j = lx; j <= rx; ++j) {
        long double ny =
            (1.0 * (y[i + 1] - y[i]) * (j - x[i]) / (x[i + 1] - x[i]));
        int u = ny + y[i] - 2;
        if (ok1) {
          if (!cw(i, i + 1, j, u)) {
            ++u;
            while (!cw(i, i + 1, j, u)) {
              ++u;
            }
            down[j + A] = u;
          } else {
            while (cw(i, i + 1, j, u + 1)) ++u;
            up[j + A] = u;
          }
        }
        if (ok2) {
          if (!ccw(i, i + 1, j, u)) {
            ++u;
            while (!ccw(i, i + 1, j, u)) {
              ++u;
            }
            down[j + A] = u;
          } else {
            while (ccw(i, i + 1, j, u + 1)) ++u;
            up[j + A] = u;
          }
        }
      }
  }
  long double ret = 0;
  long long sum = 0, total = 0;
  for (int i = -A; i <= A; ++i) {
    if (up[i + A] >= down[i + A]) {
      total += (up[i + A] - down[i + A] + 1);
      ret += 1LL * i * i * (up[i + A] - down[i + A] + 1);
      sum += 1LL * i * (up[i + A] - down[i + A] + 1);
    }
  }
  for (int i = -A; i <= A; ++i) {
    if (up[i + A] >= down[i + A]) {
      ret -= 1.0 * i * (up[i + A] - down[i + A] + 1) / total * sum;
    }
  }
  return ret / (total - 1);
}
int main() {
  int n;
  scanf("%d", &n);
  for (int i = 0; i < n; ++i) scanf("%d%d", &x[i], &y[i]);
  x[n] = x[0];
  y[n] = y[0];
  double ans = solveX(n);
  for (int i = 0; i <= n; ++i) swap(x[i], y[i]);
  memset(up, 0, sizeof(up));
  memset(down, 0, sizeof(down));
  ans += solveX(n);
  printf("%.7lf\n", ans);
  return 0;
}