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 OFFSET = 1000100;
const double oo = 1e18;
const double EPS = 1e-8;
int n, x[100100], y[100100];
double yLow[2000200], yHigh[2000200];
int main() {
  cin >> n;
  for (int i = 0; i < n; i++)
    scanf("%d%d", x + i, y + i), x[i] += OFFSET, y[i] += OFFSET;
  x[n] = x[0];
  y[n] = y[0];
  int xLow = x[0], xHigh = x[0];
  for (int i = 1; i < n; i++) {
    xLow = min(xLow, x[i]);
    xHigh = max(xHigh, x[i]);
  }
  for (int i = xLow; i <= xHigh; i++) yLow[i] = oo, yHigh[i] = -oo;
  for (int i = 0; i < n; i++)
    if (x[i] == x[i + 1]) {
      yLow[x[i]] = min(yLow[x[i]], 1.0 * min(y[i], y[i + 1]));
      yHigh[x[i]] = min(yHigh[x[i]], 1.0 * max(y[i], y[i + 1]));
    } else {
      double A = y[i] - y[i + 1], B = x[i + 1] - x[i], C = -A * x[i] - B * y[i];
      int xL = min(x[i], x[i + 1]), xR = max(x[i], x[i + 1]);
      for (int curX = xL; curX <= xR; curX++) {
        double curY = (-C - A * curX) / B;
        yLow[curX] = min(yLow[curX], curY);
        yHigh[curX] = max(yHigh[curX], curY);
      }
    }
  double sumX = 0, sumY = 0, sumXSqr = 0, sumYSqr = 0, point = 0;
  for (int curX = xLow; curX <= xHigh; curX++) {
    int ylow = int(yLow[curX] + 1 - EPS), yhigh = int(yHigh[curX] + EPS);
    point += yhigh - ylow + 1;
    sumX += (yhigh - ylow + 1.0) * curX;
    sumXSqr += (yhigh - ylow + 1.0) * curX * curX;
    sumY += (yhigh + ylow) * (yhigh - ylow + 1.0) / 2;
    sumYSqr += yhigh * (yhigh + 1.0) * (yhigh * 2 + 1) / 6 -
               (ylow - 1.0) * (ylow) * (ylow * 2 - 1) / 6;
  }
  double ans = (sumXSqr + sumYSqr) - (sumX * sumX + sumY * sumY) / point;
  ans /= (point - 1);
  printf("%.12lf\n", ans);
}