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 MAX = 100000 + 10;
int n;
struct point {
  int first, second;
  point(int a, int b) : first(a), second(b) {}
  point() {}
} d[MAX];
long long chaji(const point& s, const point& a, const point& b) {
  return (long long)(a.first - s.first) * (b.second - s.second) -
         (long long)(a.second - s.second) * (b.first - s.first);
}
const int INF = 100000000;
const int MAXL = 2000000 + 10;
const int DELTA = 1000000;
int up[MAXL], down[MAXL];
long double get(point a, point b, long double s) {
  long double r = (s - a.first) / (b.first - a.first);
  return r * (b.second - a.second) + a.second;
}
long double calc() {
  int i;
  long double S = 0;
  for ((i) = (0); (i) != (n); ++(i))
    S += chaji(point(0, 0), d[i], d[(i + 1) % n]);
  if (S < 0) reverse(d, d + n);
  for ((i) = (-DELTA); (i) <= (DELTA); ++(i)) {
    up[i + DELTA] = -INF;
    down[i + DELTA] = INF;
  }
  for ((i) = (0); (i) != (n); ++(i)) {
    int j = (i + 1) % n;
    int k;
    if (d[i].first < d[j].first)
      for ((k) = (d[i].first); (k) <= (d[j].first); ++(k)) {
        int second = ceil(get(d[i], d[j], k));
        while (chaji(d[i], d[j], point(k, second - 1)) >= 0) --second;
        down[k + DELTA] = second;
      }
    else if (d[i].first > d[j].first)
      for (k = d[i].first; k >= d[j].first; --k) {
        int second = floor(get(d[i], d[j], k));
        while (chaji(d[i], d[j], point(k, second + 1)) >= 0) ++second;
        up[k + DELTA] = second;
      }
    else {
      int l = d[i].second, r = d[j].second;
      if (l > r) swap(l, r);
      up[d[i].first + DELTA] = max(r, up[d[i].first + DELTA]);
      down[d[i].first + DELTA] = min(l, down[d[i].first + DELTA]);
    }
  }
  long double tot = 0, tot2 = 0, all = 0;
  for ((i) = (-DELTA); (i) <= (DELTA); ++(i))
    if (up[i + DELTA] >= down[i + DELTA]) {
      long double num = up[i + DELTA] - down[i + DELTA] + 1;
      tot += num * i;
      tot2 += num * i * i;
      all += num;
    }
  long double ans = 0;
  long double div = all * (all - 1);
  for ((i) = (-DELTA); (i) <= (DELTA); ++(i))
    if (up[i + DELTA] >= down[i + DELTA]) {
      long double num = up[i + DELTA] - down[i + DELTA] + 1;
      ans += num * i * i / div * all;
      ans -= num * 2 * i / div * tot;
      ans += num / div * tot2;
    }
  return ans;
}
int main() {
  int i;
  scanf("%d", &n);
  for ((i) = (0); (i) != (n); ++(i)) scanf("%d%d", &d[i].first, &d[i].second);
  long double ans = 0;
  ans = calc();
  for ((i) = (0); (i) != (n); ++(i)) swap(d[i].first, d[i].second);
  ans += calc();
  printf("%.15lf", (double)ans / 2);
  return 0;
}