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, s[100005][2], fn[2000005];
double ans, ptot, f[2000005][3];
void makeline(double x0, double y0, double x1, double y1, double *a, double *b,
              double *c) {
  *a = y1 - y0;
  *b = x0 - x1;
  *c = x1 * y0 - y1 * x0;
  return;
}
double intersection(double a, double b, double c, double x) {
  if (a == 0)
    return -c / b;
  else
    return (-c - a * x) / b;
}
void calc(void) {
  int i, j, l, r, left = LONG_MAX, right = -LONG_MAX, dx;
  double a0, b0, c0, del2, co1, co2;
  ptot = 0;
  memset(f, 0, sizeof(f));
  memset(fn, 0, sizeof(fn));
  for (i = 0; i < n; i++) {
    makeline(s[i][0], s[i][1], s[i + 1][0], s[i + 1][1], &a0, &b0, &c0);
    l = s[i][0];
    r = s[i + 1][0];
    if (l <= r)
      dx = 1;
    else
      dx = -1;
    if (b0 == 0) {
      f[s[i][0]][++fn[s[i][0]]] = s[i][1];
      continue;
    }
    left = min(left, min(s[i][0], s[i + 1][0]));
    right = max(right, max(s[i][0], s[i + 1][0]));
    for (j = l; j != r; j += dx) f[j][++fn[j]] = intersection(a0, b0, c0, j);
  }
  for (i = left, del2 = co1 = co2 = 0; i <= right; i++) {
    if (f[i][1] > f[i][2]) swap(f[i][1], f[i][2]);
    if (fn[i] == 1)
      f[i][0] = 1;
    else
      f[i][0] = floor(f[i][2] + 1e-6) - ceil(f[i][1] - 1e-6) + 1;
    ptot += f[i][0];
    co2 += co1;
    ans += f[i][0] * co2;
    co1 += del2 + f[i][0];
    del2 += f[i][0] * 2;
  }
  return;
}
int main() {
  int i;
  scanf("%d", &n);
  for (i = 0; i < n; i++)
    scanf("%d%d", &s[i][0], &s[i][1]), s[i][0] += 1000000, s[i][1] += 1000000;
  s[n][0] = s[0][0];
  s[n][1] = s[0][1];
  ans = 0;
  calc();
  for (i = 0; i <= n; i++) swap(s[i][0], s[i][1]);
  calc();
  ans /= ptot * (ptot - 1);
  printf("%.8lf\n", ans);
  return 0;
}