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 maxn = 1e5 + 5;
int N, X[maxn], Y[maxn];
double S0, S1, S2;
int p(int x) {
  int ret = (((x)-1 + N) % N);
  while (X[ret] == X[x] && Y[ret] == Y[x]) ret = (((ret)-1 + N) % N);
  return ret;
}
int s(int x) {
  int ret = (((x) + 1) % N);
  while (X[ret] == X[x] && Y[ret] == Y[x]) ret = (((ret) + 1) % N);
  return ret;
}
bool Work(int x, int &uu, int &dd, int X[], int Y[]) {
  int u, d;
  if (uu != dd) {
    u = (X[p(uu)] > X[s(uu)] ? p(uu) : s(uu));
    d = (X[p(dd)] > X[s(dd)] ? p(dd) : s(dd));
  } else if (Y[p(uu)] > Y[s(uu)])
    u = p(uu), d = s(uu);
  else
    u = s(uu), d = p(uu);
  if (x > X[u]) return false;
  double t, b;
  t = Y[uu] +
      floorl((long double)(Y[u] - Y[uu]) * (x - X[uu]) / (X[u] - X[uu]));
  b = Y[dd] + ceill((long double)(Y[d] - Y[dd]) * (x - X[dd]) / (X[d] - X[dd]));
  S0 += t - b + 1;
  S1 += (t - b + 1) * (t + b) / 2;
  S2 += (t * (t + 1) * (2 * t + 1) - (b - 1) * b * (2 * b - 1)) / 6;
  if (x == X[u]) uu = u;
  if (x == X[d]) dd = d;
  return true;
}
int main() {
  scanf("%d", &N);
  for (int i = 0; i < N; i++) scanf("%d%d", &X[i], &Y[i]);
  int Lu(0), Ld(0), Dl(0), Dr(0);
  for (int i = 1; i < N; i++) {
    if (X[Lu] > X[i] || X[Lu] == X[i] && Y[Lu] < Y[i]) Lu = i;
    if (X[Ld] > X[i] || X[Ld] == X[i] && Y[Ld] > Y[i]) Ld = i;
    if (Y[Dl] > Y[i] || Y[Dl] == Y[i] && X[Dl] > X[i]) Dl = i;
    if (Y[Dr] > Y[i] || Y[Dr] == Y[i] && X[Dr] < X[i]) Dr = i;
  }
  double ans = 0;
  for (int x = X[Lu], uu = Lu, dd = Ld; Work(x, uu, dd, X, Y); x++)
    ;
  ans += (S0 * S2 - S1 * S1) / (S0 * (S0 - 1)) * 2;
  S0 = S1 = S2 = 0;
  for (int y = Y[Dl], ll = Dl, rr = Dr; Work(y, rr, ll, Y, X); y++)
    ;
  ans += (S0 * S2 - S1 * S1) / (S0 * (S0 - 1)) * 2;
  printf("%.10f\n", ans / 2);
  return 0;
}