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>
const int MAXN = 100005;
const int SZ = 2000005;
const int INF = 0x3f3f3f3f;
const double EPS = 1e-10;
struct Point {
  int x, y;
};
long long cross(const Point &x, const Point &y) {
  return (long long)x.x * y.y - (long long)x.y * y.x;
}
int n;
Point a[MAXN];
int left[SZ];
int right[SZ];
int cc[SZ];
void init() {
  const int SZ2 = 1000002;
  scanf("%d", &n);
  for (int i = 0; i < n; ++i) {
    scanf("%d%d", &a[i].x, &a[i].y);
    a[i].x += SZ2;
    a[i].y += SZ2;
  }
  long long sum = 0;
  for (int i = 0; i < n; ++i) sum += cross(a[i], a[(i + 1) % n]);
  if (sum < 0) std::reverse(a + 1, a + n);
}
void work(long long &cnt, double &sum) {
  memset(left, INF, sizeof(left));
  memset(right, -INF, sizeof(right));
  for (int i = 0; i < n; ++i) {
    int x1 = a[i].x;
    int x2 = a[(i + 1) % n].x;
    int y1 = a[i].y;
    int y2 = a[(i + 1) % n].y;
    int minx = std::min(x1, x2);
    int maxx = std::max(x1, x2);
    for (int j = minx; j <= maxx; ++j) {
      double y = (double)(j - x1) / (x2 - x1) * (y2 - y1) + y1;
      if (x1 < x2) left[j] = (int)(y + 1 - EPS);
      if (x1 > x2) right[j] = (int)(y + EPS);
    }
  }
  cnt = 0;
  for (int i = 0; i < SZ; ++i)
    if (left[i] <= right[i])
      cnt += cc[i] = right[i] - left[i] + 1;
    else
      cc[i] = 0;
  double p1 = 0;
  double p2 = 0;
  double p3 = 0;
  sum = 0;
  for (int i = 0; i < SZ; ++i) {
    sum += cc[i] * p1;
    p3 += cc[i];
    p2 += 2 * p3 - cc[i];
    p1 += p2;
  }
}
void solve() {
  long long cnt;
  double sumx, sumy;
  work(cnt, sumy);
  for (int i = 0; i < n; ++i) std::swap(a[i].x, a[i].y);
  std::reverse(a + 1, a + n);
  work(cnt, sumx);
  printf("%.12f\n", (sumx + sumy) / 2 / ((double)cnt * (cnt - 1) / 2));
}
int main() {
  init();
  solve();
  return 0;
}