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>
int n, minn = 1e9, maxx;
int x[200100], y[200100], s = 1, ss = 1;
double ans, sum, cnt[2000100], tot;
int main() {
  int i, j, h, t, p1, p2;
  double pp1, pp2;
  scanf("%d", &n);
  for (i = 1; i <= n; ++i) {
    scanf("%d%d", x + i, y + i);
    x[i] += 1000000;
    y[i] += 1000000;
    x[n + i] = x[i];
    y[n + i] = y[i];
    if (x[i] < x[s]) s = i;
    if (x[i] > x[ss]) ss = i;
  }
  minn = 1e9;
  maxx = 0;
  for (i = 1; i <= n; ++i)
    if (x[i] == x[s]) {
      if (y[i] < minn) minn = y[i];
      if (maxx < y[i]) maxx = y[i];
    }
  cnt[x[s]] = maxx - minn + 1;
  minn = 1e9;
  maxx = 0;
  for (i = 1; i <= n; ++i)
    if (x[i] == x[ss]) {
      if (y[i] < minn) minn = y[i];
      if (maxx < y[i]) maxx = y[i];
    }
  cnt[x[ss]] = maxx - minn + 1;
  h = s;
  t = s + n;
  for (i = x[s] + 1; i < x[ss]; ++i) {
    while (x[h + 1] < i) ++h;
    while (x[t - 1] < i) --t;
    pp1 = ((double)y[h + 1] - y[h]) * (i - x[h]) / (x[h + 1] - x[h]) + y[h];
    pp2 = ((double)y[t - 1] - y[t]) * (i - x[t]) / (x[t - 1] - x[t]) + y[t];
    p1 = pp1 + 1e-3;
    p2 = pp2 + 1e-3;
    if (pp1 < pp2) {
      if (((long long)y[h + 1] - y[h]) * (i - x[h]) % (x[h + 1] - x[h]) == 0)
        --p1;
      cnt[i] = p2 - p1;
    } else {
      if (((long long)y[t - 1] - y[t]) * (i - x[t]) % (x[t - 1] - x[t]) == 0)
        --p2;
      cnt[i] = p1 - p2;
    }
  }
  tot = sum = 0.0;
  for (i = x[s]; i <= x[ss]; ++i) {
    tot += cnt[i];
    sum += (double)cnt[i] * i;
  }
  for (i = x[s]; i <= x[ss]; ++i)
    ans += tot * 2 * cnt[i] * i * i - 2 * cnt[i] * i * sum;
  s = ss = 1;
  for (i = 1; i <= n; ++i) {
    if (y[i] < y[s]) s = i;
    if (y[i] > y[ss]) ss = i;
  }
  minn = 1e9;
  maxx = 0;
  for (i = 1; i <= n; ++i)
    if (y[i] == y[s]) {
      if (x[i] < minn) minn = x[i];
      if (maxx < x[i]) maxx = x[i];
    }
  cnt[y[s]] = maxx - minn + 1;
  minn = 1e9;
  maxx = 0;
  for (i = 1; i <= n; ++i)
    if (y[i] == y[ss]) {
      if (x[i] < minn) minn = x[i];
      if (maxx < x[i]) maxx = x[i];
    }
  cnt[y[ss]] = maxx - minn + 1;
  h = s;
  t = s + n;
  for (i = y[s] + 1; i < y[ss]; ++i) {
    while (y[h + 1] < i) ++h;
    while (y[t - 1] < i) --t;
    pp1 = ((double)x[h + 1] - x[h]) * (i - y[h]) / (y[h + 1] - y[h]) + x[h];
    pp2 = ((double)x[t - 1] - x[t]) * (i - y[t]) / (y[t - 1] - y[t]) + x[t];
    p1 = pp1 + 1e-3;
    p2 = pp2 + 1e-3;
    if (pp1 < pp2) {
      if (((long long)x[h + 1] - x[h]) * (i - y[h]) % (y[h + 1] - y[h]) == 0)
        --p1;
      cnt[i] = p2 - p1;
    } else {
      if (((long long)x[t - 1] - x[t]) * (i - y[t]) % (y[t - 1] - y[t]) == 0)
        --p2;
      cnt[i] = p1 - p2;
    }
  }
  tot = sum = 0.0;
  for (i = y[s]; i <= y[ss]; ++i) {
    tot += cnt[i];
    sum += (double)cnt[i] * i;
  }
  for (i = y[s]; i <= y[ss]; ++i)
    ans += tot * 2 * cnt[i] * i * i - 2 * cnt[i] * i * sum;
  printf("%.7lf\n", ans / tot / (tot - 1.0) / 2);
  return 0;
}