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 Min[(1 << 21)];
int Max[(1 << 21)];
int X[(1 << 21)];
int Y[(1 << 21)];
double f(int n) {
  int i, j;
  for (i = (0); i < ((1 << 21)); ++i) {
    Min[i] = (1 << 21);
    Max[i] = 0;
  }
  for (i = (0); i < (n); ++i) {
    int x1 = X[i];
    int y1 = Y[i];
    int x2 = X[(i + 1) % n];
    int y2 = Y[(i + 1) % n];
    if (pair<int, int>(x1, y1) > pair<int, int>(x2, y2)) {
      swap(x1, x2);
      swap(y1, y2);
    }
    if (x1 == x2) {
      Min[x1] = min(Min[x1], y1 - 1);
      Max[x1] = max(Max[x1], y2 + 1);
      continue;
    }
    for (j = (x1); j < (x2 + 1); ++j) {
      long long l = x2 - j;
      long long r = j - x1;
      long long d = x2 - x1;
      long long v = y1 * l + y2 * r;
      Min[j] = min(Min[j], int((v - 1) / d));
      Max[j] = max(Max[j], int((v + d) / d));
    }
  }
  long double sum0 = 0;
  long double sum1 = 0;
  long double sum2 = 0;
  for (i = (0); i < ((1 << 21)); ++i)
    if (Min[i] < Max[i]) {
      long long cnt = Max[i] - Min[i] - 1;
      long long value = i;
      sum0 += cnt;
      sum1 += cnt * value;
      sum2 += cnt * value * value;
    }
  return sum0 < 1.5 ? 0.0 : (sum2 * sum0 - sum1 * sum1) / (sum0 * (sum0 - 1));
}
int main() {
  int n;
  scanf("%d", &n);
  int i, j;
  for (i = (0); i < (n); ++i) scanf("%d%d", &X[i], &Y[i]);
  for (i = (0); i < (n); ++i) {
    X[i] += (1 << 21) / 2;
    Y[i] += (1 << 21) / 2;
  }
  double res = 0;
  for (i = (0); i < (2); ++i) {
    res += f(n);
    for (j = (0); j < (n); ++j) swap(X[j], Y[j]);
  }
  printf("%.11lf\n", res);
  return 0;
};