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;
double calc(vector<int> &v) {
  int n = (int((v).size()));
  long double ret = 0.0;
  long double a = 0;
  long double b = 0;
  long double c = 0;
  c = v[0];
  for (int i = (int)(1), _n = (int)(n); i < _n; i++) {
    b += 2 * c - v[i - 1];
    a += b;
    ret += v[i] * (long double)a;
    c += v[i];
  }
  return 2 * ret / (c * (long double)(c - 1));
}
double solve(vector<pair<int, int> > p) {
  rotate(p.begin(), min_element((p).begin(), (p).end()), p.end());
  p.push_back(p[0]);
  int maxind = max_element((p).begin(), (p).end()) - p.begin(), cur = 0;
  int minx = p[0].first, maxx = p[maxind].first;
  vector<int> v(maxx - minx + 1);
  for (int x = minx, i = 0; x <= maxx; x++, i++) {
    if (p[cur + 1].first > p[cur].first && x == p[cur + 1].first) cur++;
    if (x == p[cur].first)
      v[i] = -p[cur].second;
    else {
      int ydiff = (p[cur + 1].second - p[cur].second) *
                  (long long)(x - p[cur].first) /
                  (p[cur + 1].first - p[cur].first);
      if ((p[cur + 1].first - p[cur].first) * (long long)ydiff <
          (p[cur + 1].second - p[cur].second) * (long long)(x - p[cur].first))
        ydiff++;
      v[i] = -(p[cur].second + ydiff);
    }
  }
  cur = maxind;
  for (int x = maxx, i = maxx - minx; x >= minx; x--, i--) {
    if (p[cur + 1].first < p[cur].first && x == p[cur + 1].first) cur++;
    if (x == p[cur].first)
      v[i] += p[cur].second + 1;
    else {
      int ydiff = (p[cur + 1].second - p[cur].second) *
                  (long long)(p[cur].first - x) /
                  (p[cur].first - p[cur + 1].first);
      if ((p[cur].first - p[cur + 1].first) * (long long)ydiff >
          (p[cur + 1].second - p[cur].second) * (long long)(p[cur].first - x))
        ydiff--;
      v[i] += p[cur].second + ydiff + 1;
    }
  }
  return calc(v);
}
inline long long cross(pair<int, int> p, pair<int, int> q1, pair<int, int> q2) {
  return (q1.first - p.first) * (long long)(q2.second - p.second) -
         (q1.second - p.second) * (long long)(q2.first - p.first);
}
int main() {
  ios::sync_with_stdio(false);
  int n;
  bool cc = false;
  cin >> n;
  vector<pair<int, int> > p(n);
  for (int i = 0, _n = (int)(n); i < _n; i++) {
    cin >> p[i].first >> p[i].second;
    if (i >= 2)
      if (cross(p[i - 2], p[i - 1], p[i]) < 0) cc = true;
  }
  if (cc) reverse((p).begin(), (p).end());
  double ans1 = solve(p);
  for (int i = 0, _n = (int)(n); i < _n; i++) swap(p[i].first, p[i].second);
  reverse((p).begin(), (p).end());
  double ans2 = solve(p);
  cout << fixed << setprecision(9) << (ans1 + ans2) / 2 << endl;
  {
    int _;
    cin >> _;
    return 0;
  }
}