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 double EPS = 1e-8;
int n;
int x[100000], y[100000];
double gao(int x[], int y[]) {
  int leftMost = min_element(x, x + n) - x;
  int minVal = *min_element(x, x + n);
  int maxVal = *max_element(x, x + n);
  int up1 = leftMost, up2 = (up1 + 1) % n;
  int down1 = leftMost, down2 = (down1 + n - 1) % n;
  double sqSum = 0.0;
  double sum = 0.0;
  double allCount = 0;
  for (int i = minVal; i <= maxVal; ++i) {
    if (i > x[up2]) {
      up1 = up2;
      up2 = (up2 + 1) % n;
    }
    if (i > x[down2]) {
      down1 = down2;
      down2 = (down2 + n - 1) % n;
    }
    int count = 0;
    if (i == x[up2] && (x[up1] == x[up2] || x[up2] == x[(up2 + 1) % n])) {
      count = 1 + (x[up1] == x[up2] ? abs(y[up1] - y[up2])
                                    : abs(y[up2] - y[(up2 + 1) % n]));
    } else if (i == x[down2] &&
               (x[down1] == x[down2] || x[down2] == x[(down2 + n - 1) % n])) {
      count =
          1 + (x[down1] == x[down2] ? abs(y[down1] - y[down2])
                                    : abs(y[down2] - y[(down2 + n - 1) % n]));
    } else {
      double ub =
          (double)(y[up1] - y[up2]) / (x[up1] - x[up2]) * (i - x[up1]) + y[up1];
      double db = (double)(y[down1] - y[down2]) / (x[down1] - x[down2]) *
                      (i - x[down1]) +
                  y[down1];
      count = floor(ub + EPS) - ceil(db - EPS) + 1;
    }
    allCount += count;
    sqSum += (double)i * i * count;
    sum += (double)i * count;
  }
  return (allCount * sqSum - sum * sum) / (allCount * (allCount - 1) / 2);
}
int main() {
  scanf("%d", &n);
  for (int i = 0; i < n; ++i) {
    scanf("%d%d", &x[i], &y[i]);
  }
  long long sgn = 0;
  for (int i = 0; i < n && sgn == 0; ++i) {
    int j = (i + 1) % n, k = (j + 1) % n;
    sgn = (long long)(x[j] - x[i]) * (y[k] - y[i]) -
          (long long)(x[k] - x[i]) * (y[j] - y[i]);
  }
  if (sgn > 0) {
    reverse(x, x + n);
    reverse(y, y + n);
  }
  double res = 0.0;
  res += gao(x, y);
  reverse(x, x + n);
  reverse(y, y + n);
  res += gao(y, x);
  res /= 2;
  printf("%.13f\n", res);
  return 0;
}