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 TPoint {
  long long x, y;
  TPoint(int x = 0, int y = 0) : x(x), y(y) {}
};
TPoint p[100011];
int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
long long lfloor(long long a, long long b);
long long lceil(long long a, long long b) {
  if (a < 0) {
    return -lfloor(-a, b);
  }
  return (a + b - 1) / b;
}
long long lfloor(long long a, long long b) {
  if (a < 0) {
    return -lceil(-a, b);
  }
  return a / b;
}
int main() {
  int N;
  scanf("%d", &N);
  for (int i = 0; i < N; ++i) {
    scanf("%I64d%I64d", &p[i].x, &p[i].y);
  }
  p[N] = p[0];
  long long S = 0;
  for (int i = 0; i < N; ++i) {
    S += (p[i + 1].y + p[i].y) * (p[i + 1].x - p[i].x);
  }
  if (S > 0) {
    reverse(p, p + N);
    p[N] = p[0];
  }
  S = std::abs(S);
  long long bord = 0;
  for (int i = 0; i < N; ++i) {
    bord += gcd(abs(p[i + 1].x - p[i].x), abs(p[i + 1].y - p[i].y));
  }
  long long total = (S + bord + 2) / 2;
  vector<TPoint> low, high, left, right;
  int m = 0;
  for (int i = 0; i < N; ++i) {
    if (p[i].x < p[m].x || (p[i].x == p[m].x && p[i].y < p[m].y)) {
      m = i;
    }
  }
  low.push_back(p[m]);
  for (int i = m + 1;; ++i) {
    i = (i + N) % N;
    if (p[i].x > p[(i + N - 1) % N].x) {
      low.push_back(p[i]);
    } else {
      break;
    }
  }
  m = 0;
  for (int i = 0; i < N; ++i) {
    if (p[i].x < p[m].x || (p[i].x == p[m].x && p[i].y > p[m].y)) {
      m = i;
    }
  }
  high.push_back(p[m]);
  for (int i = m + N - 1;; --i) {
    i = (i + N) % N;
    if (p[i].x > p[(i + 1) % N].x) {
      high.push_back(p[i]);
    } else {
      break;
    }
  }
  m = 0;
  for (int i = 0; i < N; ++i) {
    if (p[i].y < p[m].y || (p[i].y == p[m].y && p[i].x < p[m].x)) {
      m = i;
    }
  }
  left.push_back(p[m]);
  for (int i = m + N - 1;; --i) {
    i = (i + N) % N;
    if (p[i].y > p[(i + 1) % N].y) {
      left.push_back(p[i]);
    } else {
      break;
    }
  }
  m = 0;
  for (int i = 0; i < N; ++i) {
    if (p[i].y < p[m].y || (p[i].y == p[m].y && p[i].x > p[m].x)) {
      m = i;
    }
  }
  right.push_back(p[m]);
  for (int i = m + 1;; ++i) {
    i = (i + N) % N;
    if (p[i].y > p[(i + N - 1) % N].y) {
      right.push_back(p[i]);
    } else {
      break;
    }
  }
  double ex2 = 0.0, ex = 0.0;
  {
    int li = 0, hi = 0;
    for (int x = -1000001; x <= 1000001; ++x) {
      if (x < low[0].x) {
        continue;
      }
      if (x > low.back().x) {
        break;
      }
      int l = low[li].y + lceil((x - low[li].x) * (low[li + 1].y - low[li].y),
                                (low[li + 1].x - low[li].x));
      int r =
          high[hi].y + lfloor((x - high[hi].x) * (high[hi + 1].y - high[hi].y),
                              (high[hi + 1].x - high[hi].x));
      int p = (r - l + 1);
      ex2 += (double)1.0 * p * x * x;
      ex += (double)1.0 * p * x;
      if (x == low[li + 1].x) {
        ++li;
      }
      if (x == high[hi + 1].x) {
        ++hi;
      }
    }
  }
  double ey2 = 0.0, ey = 0.0;
  {
    int li = 0, ri = 0;
    for (int y = -1000001; y <= 1000001; ++y) {
      if (y < left[0].y) {
        continue;
      }
      if (y > left.back().y) {
        break;
      }
      int l =
          left[li].x + lceil((y - left[li].y) * (left[li + 1].x - left[li].x),
                             (left[li + 1].y - left[li].y));
      int r = right[ri].x +
              lfloor((y - right[ri].y) * (right[ri + 1].x - right[ri].x),
                     (right[ri + 1].y - right[ri].y));
      int p = (r - l + 1);
      ey2 += (double)1.0 * p * y * y;
      ey += (double)1.0 * p * y;
      if (y == left[li + 1].y) {
        ++li;
      }
      if (y == right[ri + 1].y) {
        ++ri;
      }
    }
  }
  ex2 /= total;
  ex /= total;
  ey2 /= total;
  ey /= total;
  double ans = ex2 - ex * ex + ey2 - ey * ey;
  ans *= 1.0 * total / (total - 1);
  printf("%.10lf", (double)ans);
  return 0;
}