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;
int n, i, x[100020], y[100020], c[2000010], low, high, kol[2000010], j;
double a1, b1, c1, a2, b2, c2, nx2, all, all2, ans, a[2000010][6];
void buildLine(double x1, double y1, double x2, double y2, double& a, double& b,
               double& c) {
  a = y2 - y1;
  b = x1 - x2;
  c = -a * x1 - b * y1;
}
void Solve() {
  for (i = 1; i <= n; i++) {
    buildLine(x[i], y[i], x[i + 1], y[i + 1], a1, b1, c1);
    if (x[i] != x[i + 1])
      for (j = min(x[i], x[i + 1]); j <= max(x[i], x[i + 1]); j++) {
        buildLine(j, 0, j, 1, a2, b2, c2);
        nx2 = -(1.0 * a1 * 1.0 * c2 - 1.0 * a2 * c1 * 1.0) /
              (1.0 * a1 * 1.0 * b2 - 1.0 * a2 * 1.0 * b1);
        a[j][++c[j]] = nx2;
      }
  }
  for (i = 0; i <= 2000000; i++)
    if (c[i]) {
      sort(a[i] + 1, a[i] + c[i] + 1);
      low = ceil(a[i][1] - 1e-9);
      high = floor(a[i][c[i]] + 1e-9);
      kol[i] = high - low + 1;
      all += kol[i];
      all2 += kol[i] * 1.0 * i;
    }
  for (i = 0; i <= 2000000; i++)
    if (c[i]) {
      ans += 1.0 * kol[i] * 1.0 * i * 1.0 * i * (1.0 * all - 1.0 * kol[i]);
      ans -= 1.0 * kol[i] * 1.0 * i * (all2 - kol[i] * 1.0 * i);
    }
}
int main(int argc, char* const argv[]) {
  scanf("%d", &n);
  for (i = 1; i <= n; i++) {
    scanf("%d%d", &x[i], &y[i]);
    x[i] += 1000000;
    y[i] += 1000000;
  }
  x[n + 1] = x[1];
  y[n + 1] = y[1];
  Solve();
  for (i = 1; i <= n + 1; i++) swap(x[i], y[i]);
  all = all2 = 0;
  for (i = 0; i <= 2000000; i++) c[i] = kol[i] = 0;
  Solve();
  printf("%.10lf\n", ans / (1.0 * all * (all - 1)));
  return 0;
}