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 M = 2e6 + 2e5;
const int N = M >> 1;
const int MX = 2e6;
const int D = 1e6;
double L[M], R[M];
int g[M];
struct pnt {
  int x, y;
  void input() { scanf("%d %d", &x, &y); }
} p[N];
int n;
double ans;
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    p[i].input();
    p[i].x += D, p[i].y += D;
  }
  function<void(int, double)> update = [&](int y, double x) {
    L[y] = min(L[y], x);
    R[y] = max(R[y], x);
  };
  for (int step = 0; step < 2; step++) {
    for (int i = 0; i <= MX; i++) L[i] = M, R[i] = -1;
    for (int i = 1; i <= n; i++) {
      update(p[i].y, p[i].x);
      int ni = i == n ? 1 : i + 1;
      if (p[i].y == p[ni].y) continue;
      double d = (p[ni].x - p[i].x) * 1.0 / (p[ni].y - p[i].y);
      double cur;
      cur = p[i].x;
      for (int j = p[i].y + 1; j < p[ni].y; j++) {
        cur += d;
        update(j, cur);
      }
      cur = p[ni].x;
      for (int j = p[ni].y + 1; j < p[i].y; j++) {
        cur += d;
        update(j, cur);
      }
    }
    long long tot = 0;
    for (int i = 0; i <= MX; i++) {
      int lx = L[i] + 0.9999999;
      int rx = R[i] + 0.0000001;
      g[i] = rx >= lx ? rx - lx + 1 : 0;
      tot += g[i];
    }
    double c = 0, d = 0, dd = 0;
    for (int i = 0; i < MX; i++) {
      double r = g[i] * 1.0 / (tot - 1);
      d = d + dd + r;
      dd = dd + r + r;
      c = c + d;
      ans += 1.0 * g[i + 1] / tot * c;
    }
    for (int i = 1; i <= n; i++) swap(p[i].x, p[i].y);
  }
  cout << fixed << setprecision(10) << ans << endl;
  return 0;
}