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 co = 1000010;
const int N = 6 * co + 10;
long long yN[N], yd[N];
long long bn[42], bd[42];
int pred[N];
int last[2 * co + 10];
int x[100010], y[100010];
int m;
void add(int xa, int ya, int xb, int yb) {
  if (xa == xb) return;
  if (xa > xb) {
    int tmp = xa;
    xa = xb;
    xb = tmp;
    tmp = ya;
    ya = yb;
    yb = tmp;
  }
  for (int xx = xa; xx <= xb; xx++) {
    m++;
    yN[m] = (long long)ya * (xb - xa) + (long long)(yb - ya) * (xx - xa);
    yd[m] = xb - xa;
    pred[m] = last[xx + co];
    last[xx + co] = m;
  }
}
int main() {
  int n;
  scanf("%d", &n);
  for (int i = 0; i < n; i++) scanf("%d %d", x + i, y + i);
  double ans = 0.0;
  for (int r = 0; r < 2; r++) {
    x[n] = x[0];
    y[n] = y[0];
    m = 0;
    for (int i = 0; i <= 2 * co; i++) last[i] = 0;
    for (int i = 0; i < n; i++) add(x[i], y[i], x[i + 1], y[i + 1]);
    double sum = 0, sq = 0, cnt = 0;
    for (int xx = -co; xx <= co; xx++) {
      int k = 0;
      int j = last[xx + co];
      while (j > 0) {
        bn[k] = yN[j];
        bd[k] = yd[j];
        k++;
        j = pred[j];
      }
      if (k == 0) continue;
      for (int i = 0; i < k; i++)
        for (int j = i + 1; j < k; j++)
          if (bn[i] * bd[j] > bn[j] * bd[i]) {
            long long tmp = bn[i];
            bn[i] = bn[j];
            bn[j] = tmp;
            tmp = bd[i];
            bd[i] = bd[j];
            bd[j] = tmp;
          }
      long long up = bn[k - 1] / bd[k - 1];
      while (up * bd[k - 1] > bn[k - 1]) up--;
      while ((up + 1) * bd[k - 1] <= bn[k - 1]) up++;
      long long down = bn[0] / bd[0];
      while (down * bd[0] < bn[0]) down++;
      while ((down - 1) * bd[0] >= bn[0]) down--;
      cnt += 1.0 * (up - down + 1);
      sum += 1.0 * xx * (up - down + 1);
      sq += 1.0 * xx * xx * (up - down + 1);
    }
    ans += (sq - sum * sum / cnt) / (cnt - 1);
    for (int i = 0; i < n; i++) {
      int tmp = x[i];
      x[i] = y[i];
      y[i] = tmp;
    }
  }
  printf("%.17lf\n", ans);
  return 0;
}