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 int N = 100010, V = 1000000, MV = 1001000, Inf = 1 << 30;
const double eps(1e-8);
int n, x[N] = {}, y[N] = {};
double ul[MV + MV] = {}, ur[MV + MV] = {}, *l = ul + MV, *r = ur + MV;
double ans = 0;
void init() {
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) scanf("%d%d", &x[i], &y[i]);
  x[n + 1] = x[1], y[n + 1] = y[1];
}
long long sqrsum(long long l, long long r) {
  if (l == 1)
    return r * (r + 1) * (r + r + 1) / 6;
  else if (l > 1)
    return sqrsum(1, r) - sqrsum(1, l - 1);
  else
    return sqrsum(1, -l) + sqrsum(1, r);
}
void work() {
  double s0 = 0, s1 = 0, s2 = 0;
  for (int i = -V; i <= V; ++i) l[i] = Inf, r[i] = -Inf;
  int lx = V, rx = -V;
  for (int i = 1; i <= n; ++i) {
    lx = min(lx, x[i]), rx = max(rx, x[i]);
    if (x[i] == x[i + 1])
      l[x[i]] = min(y[i], y[i + 1]), r[x[i]] = max(y[i], y[i + 1]);
    else {
      bool flag = false;
      if (x[i] > x[i + 1]) flag = true;
      if (flag) swap(x[i], x[i + 1]), swap(y[i], y[i + 1]);
      double t = 1.0 / (x[i + 1] - x[i]);
      for (int j = x[i]; j <= x[i + 1]; ++j) {
        double c = ((long long)(j - x[i]) * y[i + 1] +
                    (long long)(x[i + 1] - j) * y[i]) *
                   t;
        l[j] = min(l[j], c);
        r[j] = max(r[j], c);
      }
      if (flag) swap(x[i], x[i + 1]), swap(y[i], y[i + 1]);
    }
  }
  for (int i = lx; i <= rx; ++i) {
    long long tl = (int)ceil(l[i]), tr = (int)floor(r[i]);
    s0 += tr - tl + 1;
    s1 += (tr + tl) * (tr - tl + 1) / 2;
    s2 += sqrsum(tl, tr);
  }
  ans += (s0 * s2 - s1 * s1) / s0 / (s0 - 1);
}
void swapxy() {
  for (int i = 1; i <= n + 1; ++i) swap(x[i], y[i]);
}
int main() {
  init();
  work();
  swapxy();
  work();
  printf("%.10f\n", ans);
  return 0;
}