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 main() {
  int n;
  cin >> n;
  vector<int> x(n), y(n);
  for (int i = 0; i < n; ++i) {
    cin >> x[i] >> y[i];
  }
  int mx = *min_element(x.begin(), x.end());
  int my = *min_element(y.begin(), y.end());
  for (int i = 0; i < n; ++i) {
    x[i] -= mx;
    y[i] -= my;
  }
  double res = 0;
  bool isY = false;
makeY:
trap:
  int MX = *max_element(x.begin(), x.end());
  vector<int> count(MX + 1);
  for (int i = 0; i < n; ++i) {
    int x1 = x[i];
    int x2 = x[(i + 1) % n];
    int y1 = y[i];
    int y2 = y[(i + 1) % n];
    if (x1 == x2) {
      continue;
    }
    if (x1 < x2) {
      if (x2 == MX) count[x2] += y2;
      for (int X = 0; X + x1 < x2; ++X) {
        count[x1 + X] += y1;
        if (y1 <= y2) {
          count[x1 + X] += 1LL * (y2 - y1) * X / (x2 - x1);
        } else {
          count[x1 + X] -= (1LL * (y1 - y2) * X + (x2 - x1) - 1) / (x2 - x1);
        }
      }
    } else {
      if (x2 == 0) count[0] -= y2 - 1;
      for (int X = 1; X + x2 <= x1; ++X) {
        count[x2 + X] -= y2;
        if (y1 >= y2) {
          count[x2 + X] -= (1LL * (y1 - y2) * X) / (x1 - x2);
          if ((1LL * (y1 - y2) * X) % (x1 - x2) == 0) count[x2 + X]++;
        } else {
          count[x2 + X] += 1LL * (y2 - y1) * X / (x1 - x2) + 1;
        }
      }
    }
  }
  if (*min_element(count.begin(), count.end()) < 0) {
    reverse(x.begin(), x.end());
    reverse(y.begin(), y.end());
    goto trap;
  }
  double sumX = 0;
  double sumXS = 0;
  double cnt = 0;
  for (int i = 0; i <= MX; ++i) {
    res += count[i] * (sumXS - sumX * 2 * i + 1.0 * i * i * cnt);
    sumXS += 1.0 * count[i] * i * i;
    sumX += 1.0 * count[i] * i;
    cnt += count[i];
  }
  if (isY == false) {
    isY = true;
    for (int i = 0; i < n; ++i) swap(x[i], y[i]);
    goto makeY;
  }
  res /= cnt * (cnt - 1) / 2;
  printf("%.10lf\n", res / 2);
  return 0;
}