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 inv = numeric_limits<int>::max();
const int minv = numeric_limits<int>::min();
const int max_n = 100010;
const int clim = 1000010;
int n;
pair<int, int> v[max_n];
double res = 0.0;
double c[2 * clim + 1][2];
int csz[2 * clim + 1];
int miny, maxy;
void markoff(int i) {
  int j = (i + 1) % n;
  int x1 = v[i].first, y1 = v[i].second, x2 = v[j].first, y2 = v[j].second;
  if (y1 == y2)
    c[y1 - miny][csz[y1 - miny]++] = x1;
  else {
    double dx = ((double(x2 - x1)) / (abs((double(y2 - y1)))));
    double x = x1;
    for (int y = y1; y != y2; y += ((y2 - y1) / (abs(y2 - y1)))) {
      c[y - miny][csz[y - miny]++] = x;
      x += dx;
    }
  }
}
int rddn(double d) {
  if (abs(d - floor(d)) < (1.0e-12)) return (int(floor(d)));
  if (abs(d - ceil(d)) < (1.0e-12)) return (int(ceil(d)));
  return (int(floor(d)));
}
int rdup(double d) {
  if (abs(d - floor(d)) < (1.0e-12)) return (int(floor(d)));
  if (abs(d - ceil(d)) < (1.0e-12)) return (int(ceil(d)));
  return (int(ceil(d)));
}
double a[2 * clim + 1];
void finda(int y) {
  if (csz[y] == 1) {
    a[y] = 1;
    return;
  }
  double x1 = c[y][0], x2 = c[y][1];
  if (x1 > x2) swap(x1, x2);
  int rx1 = rdup(x1), rx2 = rddn(x2);
  a[y] = (double(rx2 - rx1 + 1));
}
double sa[2 * clim + 2];
void process() {
  miny = inv;
  maxy = minv;
  for (int i = 0; i < n; ++i) {
    miny = min(miny, v[i].second);
    maxy = max(maxy, v[i].second);
  }
  fill(csz, csz + maxy - miny + 1, 0);
  for (int i = 0; i < n; ++i) markoff(i);
  for (int y = 0; y <= maxy - miny; ++y) finda(y);
  sa[maxy - miny + 1] = 0.0;
  for (int y = maxy - miny; y >= 0; --y) sa[y] = sa[y + 1] + a[y];
  double Qa = 0.0;
  double dQa = a[maxy - miny];
  for (int y = maxy - miny - 1; y >= 0; --y) {
    Qa += dQa;
    res += a[y] * Qa;
    dQa += (a[y] + 2.0 * sa[y + 1]);
  }
}
int main() {
  scanf("%d", &n);
  for (int i = 0; i < n; ++i) {
    scanf("%d", &v[i].first);
    scanf("%d", &v[i].second);
  }
  process();
  for (int i = 0; i < n; ++i) swap(v[i].first, v[i].second);
  process();
  res /= (sa[0] * (sa[0] - 1.0) / 2.0);
  res /= 2.0;
  printf("%.12f", res);
  return 0;
}