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;
double x[100000], y[100000];
double Intersection(int i, int j, int level) {
  return (double)(level - y[i]) / (y[j] - y[i]) * (x[j] - x[i]) + x[i];
}
void Scan(int n, double& sum, double& square_sum, long long& ct) {
  int start = 0;
  for (int i = 1; i < n; ++i) {
    if (y[i] > y[start]) {
      start = i;
    }
  }
  int a = start, b = start;
  while (y[(b + 1) % n] == y[b]) {
    b = (b + 1) % n;
  }
  b = (b + 1) % n;
  while (y[(a - 1 + n) % n] == y[a]) {
    a = (a - 1 + n) % n;
  }
  a = (a - 1 + n) % n;
  int level = y[start];
  while (true) {
    double l = Intersection(a, (a + 1) % n, level);
    double r = Intersection(b, (b - 1 + n) % n, level);
    if (l > r) swap(l, r);
    l = ceil(l);
    r = floor(r);
    ct += r - l + 1;
    sum += (l + r) * (r - l + 1) / 2;
    --l;
    square_sum += r * (r + 1) * (2 * r + 1) / 6 - l * (l + 1) * (2 * l + 1) / 6;
    if (y[a] == level) {
      a = (a - 1 + n) % n;
      if (y[a] >= level) break;
    }
    if (y[b] == level) {
      b = (b + 1) % n;
    }
    --level;
  }
}
int main() {
  int n;
  scanf("%d", &n);
  for (int i = 0; i < n; ++i) {
    scanf("%lf%lf", x + i, y + i);
    if (i > 0 && x[i] == x[i - 1] && y[i] == y[i - 1]) {
      --i, --n;
    }
  }
  if (x[n - 1] == x[0] && y[n - 1] == y[0]) {
    --n;
  }
  double sum = 0;
  double square_sum = 0;
  long long ct = 0;
  Scan(n, sum, square_sum, ct);
  double answer = ct * square_sum - sum * sum;
  for (int i = 0; i < n; ++i) {
    swap(x[i], y[i]);
  }
  sum = 0;
  square_sum = 0;
  ct = 0;
  Scan(n, sum, square_sum, ct);
  answer += ct * square_sum - sum * sum;
  printf("%.10f\n", answer / ct / (ct - 1));
  return 0;
}