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 n, x[100007], y[100007];
double p[2000007], sum[2000007], a[2000007], b[2000007], ans = 0;
void solve() {
  int up = 0, dw = 2e6 + 1, id = 0;
  int l = 0, r = 0;
  for (int i = 0; i < n; i++) {
    up = max(up, x[i]);
    if (dw > x[i]) {
      dw = x[i];
      id = i;
    }
  }
  l = r = id;
  memset(p, 0, sizeof(p));
  memset(sum, 0, sizeof(sum));
  memset(a, 0, sizeof(a));
  memset(b, 0, sizeof(b));
  double total = 0, ret = 0;
  for (int i = dw; i <= up; i++) {
    while (x[(l - 1 + n) % n] < i) l = (l - 1 + n) % n;
    while (x[(r + 1) % n] < i) r = (r + 1) % n;
    int lef = 0, rig = 2e6;
    vector<double> pt;
    if (x[(l - 1 + n) % n] == x[l]) {
      pt.push_back(y[l]), pt.push_back(y[(l - 1 + n) % n]);
    } else {
      int pv = (l - 1 + n) % n;
      pt.push_back(1.0 * (y[pv] - y[l]) / (x[pv] - x[l]) * (i - x[l]) +
                   1.0 * y[l]);
    }
    if (x[r] == x[(r + 1) % n]) {
      pt.push_back(y[r]), pt.push_back(y[(r + 1) % n]);
    } else {
      int pv = (r + 1) % n;
      pt.push_back(1.0 * (y[pv] - y[r]) / (x[pv] - x[r]) * (i - x[r]) +
                   1.0 * y[r]);
    }
    sort(pt.begin(), pt.end());
    lef = (int)ceil(pt[0]);
    rig = (int)pt[(int)pt.size() - 1];
    p[i] = max(0, rig - lef + 1);
    total += p[i];
  }
  total = total * (total - 1) / 2LL;
  for (int i = dw; i <= up; i++) {
    p[i] /= total;
    sum[i] = sum[i - 1] + 2.0 * p[i];
  }
  for (int i = dw + 1; i <= up; i++) {
    a[i] = a[i - 1] + p[i - 1] + b[i - 1] + sum[i - 2];
    b[i] = b[i - 1] + p[i - 1] + sum[i - 2];
    ret = ret + p[i] * total * a[i];
  }
  ans += ret;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin >> n;
  for (int i = 0; i < n; i++) {
    cin >> x[i] >> y[i];
    x[i] += 1e6 + 1;
    y[i] += 1e6 + 1;
  }
  solve();
  for (int i = 0; i < n; i++) swap(x[i], y[i]);
  solve();
  cout << (fixed) << setprecision(15) << ans / 2.0;
}