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 N = 110000;
int x[N], y[N];
vector<int> vec[2];
int main() {
  int n;
  scanf("%d", &n);
  auto prv = [&n](int x) { return (x - 1 + n) % n; };
  auto nxt = [&n](int x) { return (x + 1) % n; };
  for (int i = 0; i < n; i++) scanf("%d%d", &x[i], &y[i]);
  for (int T = 0; T < 2; T++) {
    if (T)
      for (int i = 0; i < n; i++) swap(x[i], y[i]);
    int id, miy = 1e8;
    for (int i = 0; i < n; i++)
      if (miy > y[i]) miy = y[i], id = i;
    int lid = id, rid = id;
    while (y[prv(lid)] == miy) lid = prv(lid);
    while (y[nxt(rid)] == miy) rid = nxt(rid);
    vec[T].push_back(abs(x[lid] - x[rid]) + 1);
    int now_y = miy;
    while (1) {
      ++now_y;
      if (y[prv(lid)] == now_y) lid = prv(lid);
      if (y[nxt(rid)] == now_y) rid = nxt(rid);
      if (y[prv(lid)] <= y[lid]) {
        vec[T].push_back(abs(x[lid] - x[rid]) + 1);
        break;
      }
      double lx = (1.0 * x[lid] * (y[prv(lid)] - now_y) +
                   1.0 * x[prv(lid)] * (now_y - y[lid])) /
                  (y[prv(lid)] - y[lid]);
      double rx = (1.0 * x[rid] * (y[nxt(rid)] - now_y) +
                   1.0 * x[nxt(rid)] * (now_y - y[rid])) /
                  (y[nxt(rid)] - y[rid]);
      if (lx > rx) swap(lx, rx);
      vec[T].push_back(floor(rx) - ceil(lx) + 1);
    }
  }
  long long all = 0;
  for (auto &t : vec[0]) all += t;
  double ans = 0;
  for (int T = 0; T < 2; T++) {
    double sum0 = 0, sum1 = 0, sum2 = 0;
    int k = 0;
    for (auto &t : vec[T]) {
      sum0 += t;
      sum1 += 1.0 * k * t;
      sum2 += 1.0 * k * k * t;
      ++k;
    }
    ans += 2 * sum2 * sum0 - 2 * sum1 * sum1;
  }
  printf("%.10lf\n", ans / all / (all - 1) / 2);
}