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 N = 105000;
const int T = 1000000;
const int M = 2005000;
const double mi = 1e-8;
const int inf = 1987654321;
int n;
int cha;
int a[N], b[N];
int minz[M], maxz[M];
int l, r;
int cc[M];
double ans = 0.0;
long long m;
void getData() {
  int i;
  scanf("%d", &n);
  for (i = 1; i <= n; i++) {
    scanf("%d%d", &a[i], &b[i]);
    a[i] += T;
    b[i] += T;
  }
  a[n + 1] = a[1];
  b[n + 1] = b[1];
}
double fang() {
  double res = 0;
  int i;
  for (i = l; i <= r; i++) {
    double now = i - cha;
    now *= i - cha;
    now *= cc[i];
    now *= m;
    res += now;
  }
  return res;
}
double ji() {
  double res = 0.0;
  int i;
  for (i = l; i <= r; i++) {
    double now = i - cha;
    now *= cc[i];
    res += now;
  }
  res *= res;
  return res;
}
void Do(int x[], int y[]) {
  memset(minz, 0x3f, sizeof minz);
  memset(maxz, 0xc0, sizeof maxz);
  l = inf;
  r = -inf;
  int i, j;
  for (i = 1; i <= n; i++) {
    int p = x[i];
    int q = y[i];
    int s = x[i + 1];
    int t = y[i + 1];
    if (p > s) {
      swap(p, s);
      swap(q, t);
    }
    l = min(l, p);
    r = max(r, s);
    for (j = p; j <= s; j++) {
      if (p == s) {
        if (q > t) swap(q, t);
        minz[j] = min(minz[j], q);
        maxz[j] = max(maxz[j], t);
        continue;
      }
      double now = t - q;
      now *= j - p;
      now /= s - p;
      now += q;
      int zheng = floor(now + 0.5);
      if (now - zheng < mi && zheng - now < mi) {
        minz[j] = min(minz[j], zheng);
        maxz[j] = max(maxz[j], zheng);
      } else {
        int qz = floor(now);
        minz[j] = min(minz[j], qz + 1);
        maxz[j] = max(maxz[j], qz);
      }
    }
  }
  for (i = l; i <= r; i++) cc[i] = maxz[i] - minz[i] + 1;
  m = 0;
  for (i = l; i <= r; i++) m += cc[i];
  int aim = (m + 1) / 2;
  for (i = l; i <= r; i++) {
    if (aim <= cc[i]) break;
    aim -= cc[i];
  }
  cha = i;
  ans += fang();
  ans -= ji();
}
void print() {
  ans /= m;
  ans /= (m - 1);
  printf("%.8f\n", ans);
}
int main() {
  getData();
  Do(a, b);
  Do(b, a);
  print();
  return 0;
}