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;
struct Point {
  long long x, y;
  Point() {}
  Point(long long x0, long long y0) : x(x0), y(y0) {}
  void in() { scanf("%I64d %I64d", &x, &y); }
  long long operator*(Point pt) { return x * pt.y - y * pt.x; }
  Point operator-(Point pt) { return Point(x - pt.x, y - pt.y); }
} p[100010];
long long judge1(long long y, Point a, Point b) {
  if (a.y == b.y) return min(a.x, b.x);
  long long left = -2000000;
  long long right = 2000000;
  long long ans;
  while (right >= left) {
    long long mid = (left + right) / 2;
    Point o = Point(mid, y);
    if ((b - a) * (o - a) > 0)
      left = mid + 1;
    else {
      ans = mid;
      right = mid - 1;
    }
  }
  return ans;
}
long long judge2(long long y, Point a, Point b) {
  if (a.y == b.y) return max(a.x, b.x);
  long long left = -2000000;
  long long right = 2000000;
  long long ans;
  while (right >= left) {
    long long mid = (left + right) / 2;
    Point o = Point(mid, y);
    if ((b - a) * (o - a) >= 0) {
      ans = mid;
      left = mid + 1;
    } else
      right = mid - 1;
  }
  return ans;
}
long long x[2000010];
int n;
double solve() {
  p[n] = p[0];
  p[n + 1] = p[1];
  bool need = false;
  for (int i = 0; i < n; i++) {
    if ((p[i + 1] - p[i]) * (p[i + 2] - p[i]) == 0) continue;
    if ((p[i + 1] - p[i]) * (p[i + 2] - p[i]) < 0) {
      need = true;
      break;
    }
  }
  if (need) reverse(p, p + n);
  p[n] = p[0];
  p[n + 1] = p[1];
  long long left = (1LL) << 60;
  long long right = -(1LL) << 60;
  int begin = 0;
  for (int i = 0; i < n; i++) {
    if (p[i].y < left) {
      left = p[i].y;
      begin = i;
    }
    if (p[i].y > right) right = p[i].y;
  }
  int l, r, ll, rr;
  l = r = begin;
  for (long long t = left; t <= right; t++) {
    while (1) {
      ll = (l - 1 + n) % n;
      if (p[ll].y > t || p[ll].y == right) break;
      l = ll;
    }
    while (1) {
      rr = (r + 1) % n;
      if (p[rr].y > t || p[rr].y == right) break;
      r = rr;
    }
    long long a = judge1(t, p[l], p[ll]);
    long long b = judge2(t, p[r], p[rr]);
    x[t - left] = b - a + 1;
  }
  double T = 0;
  for (int i = left; i <= right; i++) T += x[i - left];
  double ans = 0;
  double a0 = 0;
  double a1 = 0;
  double a2 = 0;
  for (int t = left; t < right; t++) {
    a1 += a0 + x[t - left];
    a2 += a1;
    a0 += x[t - left] * 2;
    ans += a2 * x[t - left + 1];
  }
  ans /= T;
  ans /= T - 1.0;
  return ans;
}
int main() {
  scanf("%d", &n);
  for (int i = 0; i < n; i++) p[i].in();
  double ans = 0;
  ans += solve();
  for (int i = 0; i < n; i++) swap(p[i].x, p[i].y);
  ans += solve();
  printf("%.12f\n", ans);
  return 0;
}