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 point {
  int x, y;
  void scan() { scanf("%d%d", &x, &y); }
} x[110000];
int n, L, R, U, D;
long double num[2100000];
long double *A;
long double get(point k1, point k2, int k3) {
  if (k1.x == k2.x) return k2.y;
  return (long double)(k3 - k1.x) / (long double)(k2.x - k1.x) * (k2.y - k1.y) +
         k1.y;
}
int pre(int k) { return (k - 2 + n) % n + 1; }
int next(int k) { return k % n + 1; }
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) x[i].scan();
  A = num + 1005000;
  L = 1e7;
  R = -1e7;
  for (int i = 1; i <= n; i++) {
    L = min(L, x[i].x);
    R = max(R, x[i].x);
  }
  int l, r;
  for (int i = 1; i <= n; i++)
    if (x[i].x == L) {
      l = i;
      r = i;
      break;
    }
  for (int i = L; i <= R; i++) {
    while (x[l].x <= i && x[l].x != R) l = pre(l);
    while (x[r].x <= i && x[r].x != R) r = next(r);
    long double k3 = get(x[l], x[next(l)], i), k4 = get(x[r], x[pre(r)], i);
    if (k3 > k4) swap(k3, k4);
    int k1 = floor(k3 - 1e-7) + 1, k2 = floor(k4 + 1e-7);
    A[i] = k2 - k1 + 1;
  }
  long double ans = 0, tot = 0, sum = 0;
  for (int i = L; i <= R; i++) {
    tot += A[i];
    sum += A[i] * i;
  }
  for (int i = L; i <= R; i++) {
    ans += -sum * 2 * A[i] * i + A[i] * (A[i] + 1) * (long double)i * i +
           (long double)i * i * A[i] * (tot - 1);
    sum -= A[i] * i;
  }
  memset(num, 0x00, sizeof num);
  for (int i = 1; i <= n; i++) swap(x[i].x, x[i].y);
  L = 1e7;
  R = -1e7;
  for (int i = 1; i <= n; i++) {
    L = min(L, x[i].x);
    R = max(R, x[i].x);
  }
  for (int i = 1; i <= n; i++)
    if (x[i].x == L) {
      l = i;
      r = i;
      break;
    }
  for (int i = L; i <= R; i++) {
    while (x[l].x <= i && x[l].x != R) l = pre(l);
    while (x[r].x <= i && x[r].x != R) r = next(r);
    long double k3 = get(x[l], x[next(l)], i), k4 = get(x[r], x[pre(r)], i);
    if (k3 > k4) swap(k3, k4);
    int k1 = floor(k3 - 1e-7) + 1, k2 = floor(k4 + 1e-7);
    A[i] = k2 - k1 + 1;
  }
  tot = 0, sum = 0;
  for (int i = L; i <= R; i++) {
    tot += A[i];
    sum += A[i] * i;
  }
  for (int i = L; i <= R; i++) {
    ans += -sum * 2 * A[i] * i + A[i] * (A[i] + 1) * (long double)i * i +
           (long double)i * i * A[i] * (tot - 1);
    sum -= A[i] * i;
  }
  printf("%.11lf\n", (double)(ans / tot / (tot - 1)));
  return 0;
}