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 MAX_SIZE = 100000;
const int INF = 0x3f3f3f3f;
struct Point {
  int x, y;
};
inline Point operator-(const Point& a, const Point& b) {
  Point ans;
  ans.x = a.x - b.x;
  ans.y = a.y - b.y;
  return ans;
}
inline long long det(const Point& a, const Point& b) {
  return (long long)a.x * b.y - a.y * b.x;
}
int minn, maxn;
int n;
Point data[MAX_SIZE * 2 + 10];
long double xsqtot, ysqtot, xtot, ytot;
long long cnt;
inline void update(int x, int l, int r) {
  if (l > r) return;
  cnt += r - l + 1;
  xsqtot += (long double)x * x * (r - l + 1);
  ysqtot += ((long double)r * (r + 1) * ((r << 1) + 1) -
             (long double)(l - 1) * l * (((l - 1) << 1) + 1)) /
            6.0;
  xtot += (long double)x * (r - l + 1);
  ytot += (long double)(l + r) * (r - l + 1) / 2.0;
}
inline void findRange(int x, int& low, int& high) {
  low = INF;
  high = -INF;
  for (int i = 1; i <= n; i++)
    if (data[i].x == x) {
      if (data[i].y < low) low = data[i].y;
      if (data[i].y > high) high = data[i].y;
    }
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%d%d", &data[i].x, &data[i].y);
    data[i].y += 1000001;
  }
  long long tot = 0;
  for (int i = 2; i < n; i++)
    tot += det(data[i] - data[1], data[i + 1] - data[i]);
  if (tot < 0) reverse(data + 1, data + n + 1);
  minn = INF;
  maxn = -INF;
  for (int i = 1; i <= n; i++) {
    if (data[i].x < minn) minn = data[i].x;
    if (data[i].x > maxn) maxn = data[i].x;
  }
  int L = 1, R = n;
  while (data[L].x != maxn) data[++R] = data[L++];
  data[++R] = data[L];
  int mid;
  for (mid = L; data[mid].x != minn; mid++)
    ;
  int pl = mid, pr = mid;
  for (int x = minn; x <= maxn; x++) {
    int high, low;
    if (x == minn || x == maxn)
      findRange(x, low, high);
    else {
      while (pl > L && data[pl].x <= x) --pl;
      while (pr < R && data[pr].x <= x) ++pr;
      high = (int)(((long long)(x - data[pl + 1].x) *
                        (data[pl].y - data[pl + 1].y) +
                    (long long)data[pl + 1].y * (data[pl].x - data[pl + 1].x)) /
                   (data[pl].x - data[pl + 1].x));
      low = (int)(((long long)(x - data[pr - 1].x) *
                       (data[pr].y - data[pr - 1].y) +
                   (long long)data[pr - 1].y * (data[pr].x - data[pr - 1].x)) /
                      (data[pr].x - data[pr - 1].x) +
                  ((long long)(x - data[pr - 1].x) *
                       (data[pr].y - data[pr - 1].y) %
                       (data[pr].x - data[pr - 1].x) !=
                   0));
    }
    update(x, low, high);
  }
  long double ans =
      ((xsqtot + ysqtot) -
       ((xtot * xtot - xsqtot) + (ytot * ytot - ysqtot)) / (cnt - 1)) /
      cnt;
  printf("%.10f\n", (double)ans);
  return 0;
}