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;
struct Tpoint {
  long long x, y;
  const bool operator!=(Tpoint a) const { return (a.x != x) || (a.y != y); }
} P[100050];
struct Tline {
  Tpoint p0, p1;
} L[100050];
double s1[2000050], s2[2000050], s3[2000050];
long long cnt[2000050];
int n, tot, m;
bool cmp(Tline a, Tline b) {
  return (a.p0.x < b.p0.x) || ((a.p0.x == b.p0.x) && (a.p1.y < b.p1.y));
}
double work() {
  Tpoint _p, _p0, _p1;
  double ans;
  long long i, A, B, _L, _R;
  tot = 0;
  for (i = 0; i <= n - 1; i++)
    if (P[i].x != P[(i + 1) % n].x) {
      tot++;
      L[tot].p0 = P[i];
      L[tot].p1 = P[(i + 1) % n];
      if (L[tot].p0.x > L[tot].p1.x) {
        swap(L[tot].p0, L[tot].p1);
      }
    }
  sort(L + 1, L + tot + 1, cmp);
  A = 1;
  B = 2;
  m = L[tot].p1.x - L[1].p0.x + 1;
  cnt[1] = L[2].p0.y - L[1].p0.y + 1;
  for (i = L[1].p0.x + 1; i <= L[tot].p1.x; i++) {
    if (i > L[A].p1.x) {
      _p = L[A].p1;
      while (L[A].p0 != _p) A++;
    }
    _p0 = L[A].p0;
    _p1 = L[A].p1;
    if (_p0.y > _p1.y) swap(_p0, _p1);
    _L = _p0.y + (llabs(i - _p0.x) * (_p1.y - _p0.y)) / llabs(_p1.x - _p0.x);
    if ((llabs(i - _p0.x) * (_p1.y - _p0.y)) % llabs(_p1.x - _p0.x)) _L++;
    if (i > L[B].p1.x) {
      _p = L[B].p1;
      while (L[B].p0 != _p) B++;
    }
    _p0 = L[B].p0;
    _p1 = L[B].p1;
    if (_p0.y > _p1.y) swap(_p0, _p1);
    _R = _p0.y + (llabs(i - _p0.x) * (_p1.y - _p0.y)) / llabs(_p1.x - _p0.x);
    cnt[i - L[1].p0.x + 1] = _R - _L + 1;
  }
  s1[0] = 0;
  s2[0] = 0;
  s3[0] = 0;
  ans = 0;
  for (i = 1; i <= m; i++) s1[i] = s1[i - 1] + cnt[i];
  for (i = 1; i <= m; i++) s2[i] = s2[i - 1] + 2 * s1[i - 1] + cnt[i];
  for (i = 1; i <= m; i++) s3[i] = s3[i - 1] + s2[i];
  for (i = 1; i <= m; i++) ans += s3[i - 1] * cnt[i];
  ans /= s1[m] * (s1[m] - 1);
  return ans;
}
int main() {
  double ans;
  int i;
  scanf("%d", &n);
  for (i = 0; i <= n - 1; i++) {
    scanf("%I64d%I64d", &P[i].x, &P[i].y);
    P[i].x += 1000000;
    P[i].y += 1000000;
  }
  ans = work();
  for (i = 0; i <= n - 1; i++) swap(P[i].x, P[i].y);
  ans += work();
  printf("%.10lf\n", ans);
  return 0;
}