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 {
  double x, y;
  point() { x = y = 0; }
  point(double _x, double _y) { x = _x, y = _y; }
  void read() { scanf("%lf%lf", &x, &y); }
  point operator-(point &a) { return point(x - a.x, y - a.y); }
  double operator*(point a) { return x * a.y - y * a.x; }
} a[200005];
int n, l, r, p;
double up, down, c[2000005], second[2000005], q[2000005];
bool cmp(point &a, point &b) {
  return ((a.x < b.x) || (a.x == b.x && a.y < b.y));
}
void Up(point &a, point &b, int i) {
  if (a.x == b.x)
    up = max(a.y, b.y);
  else
    up = floor((a.x - i) * (a.y - b.y) / (b.x - a.x)) + a.y;
  if (b.x == i) l = (l + 1) % n;
}
void Down(point &a, point &b, int i) {
  if (a.x == b.x)
    down = min(a.y, b.y);
  else
    down = ceil((a.x - i) * (a.y - b.y) / (b.x - a.x)) + a.y;
  if (b.x == i) r = (r - 1 + n) % n;
}
int main() {
  scanf("%d", &n);
  int L = 0, R = 0;
  for (int i = 0; i < n; ++i) {
    a[i].read();
    a[i].x += 1000000;
    a[i].y += 1000000;
  }
  double S = 0;
  for (int i = 0; i < n; ++i) S += (a[i] * a[(i + 1) % n]);
  if (S > 0) reverse(a, a + n);
  for (int i = 0; i < n; ++i) {
    if (cmp(a[i], a[L])) L = i;
    if (cmp(a[R], a[i])) R = i;
  }
  int M1 = (int)a[L].x, M2 = (int)a[R].x;
  l = L, r = L;
  long double a1 = 0;
  for (int i = M1; i <= M2; ++i) {
    int j = (l + 1) % n, k = (r - 1 + n) % n;
    Up(a[l], a[j], i);
    Down(a[r], a[k], i);
    if (up + 1 < down) assert(false);
    c[i] = up - down + 1;
    second[i] = up * (up + 1) / 2 - down * (down - 1) / 2;
    q[i] = up * (up + 1) * (2 * up + 1) / 6 -
           down * (down - 1) * (2 * down - 1) / 6;
    a1 += c[i];
  }
  long double a2 = 0, a3 = 0, a4 = 0, a5 = 0;
  for (int i = M1; i <= M2; ++i) {
    a2 += q[i] / (a1 - 1), a3 += second[i];
    a4 += c[i] * i * i / (a1 - 1), a5 += c[i] * i;
  }
  long double res =
      (a2 + a4) - (a3 / (a1 - 1)) * (a3 / a1) - (a5 / (a1 - 1)) * (a5 / a1);
  printf("%.9lf", (double)res);
  return 0;
}