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;
struct point {
  int x, y;
  double k, b;
  friend double operator*(const point& A, const point& B) {
    return 1.0 * A.x * B.y - 1.0 * A.y * B.x;
  }
} a[100005];
int N;
double ans, S;
map<int, int> F;
void init() {
  scanf("%d", &N);
  for (int i = 1; i <= N; i++) scanf("%d%d", &a[i].x, &a[i].y);
}
void work() {
  a[N + 1] = a[1], S = 0, F.clear();
  double area = 0;
  for (int i = 1; i <= N; i++) area += a[i] * a[i + 1];
  if (area < -1e-9)
    for (int i = 1; i + i <= N + 1; i++) swap(a[i], a[N + 2 - i]);
  int mi = 1e9, ma = -1e9, l, r, t = 0;
  auto inc = [&](int i) { return i < N ? i + 1 : 1; };
  auto dec = [&](int i) { return i > 1 ? i - 1 : N; };
  for (int i = 1; i <= N; i++) {
    if (a[i].x < mi) mi = a[i].x, l = i;
    if (a[i].x > ma) ma = a[i].x, r = i;
    if (a[i].x != a[i + 1].x)
      a[i].k = 1.0 * (a[i].y - a[i + 1].y) / (a[i].x - a[i + 1].x),
      a[i].b = a[i].y - a[i].k * a[i].x;
    else
      F[a[i].x] += abs(a[i].y - a[i + 1].y) + 1, a[i].k = 1e99;
  }
  for (int x = mi, i = l, j = l; x <= ma; x++) {
    for (; dec(i) != r && a[dec(i)].x <= x; i = dec(i))
      ;
    for (; inc(j) != r && a[inc(j)].x <= x; j = inc(j))
      ;
    if (a[dec(i)].k >= 1e99 || a[j].k >= 1e99) continue;
    F[x] = floor(a[dec(i)].k * x + a[dec(i)].b + 1e-9) -
           ceil(a[j].k * x + a[j].b - 1e-9) + 1;
  }
  double u = 0, v = 0, w = 0;
  for (auto i : F)
    w += v, v += 2 * u + i.second, u += i.second, ans += w * i.second,
        S += i.second;
}
void doit() {
  work();
  for (int i = 1; i <= N; i++) swap(a[i].x, a[i].y);
  work();
  printf("%.9lf\n", 1.0 * ans / S / (S - 1));
}
int main() {
  init();
  doit();
  return 0;
}