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 double eps = 1e-8;
struct Point {
  int x, y;
} d[200005];
long double ans, s2, s1, s0;
int n;
void Work() {
  int t = 1, l = 1, r = n + 1;
  s2 = s1 = s0 = 0;
  for (int i = 1; i <= n; i++)
    if (d[i].x < d[t].x) t = i;
  for (int i = 1; i < t; i++) d[i + n] = d[i];
  for (int i = 1; i <= n; i++) d[i] = d[i + t - 1];
  while (d[l + 1].x == d[1].x) l++;
  while (d[r - 1].x == d[1].x) r--;
  l++;
  r--;
  d[n + 1] = d[1];
  for (int x = d[1].x;; x++) {
    while (d[l].x < x && l <= r) l++;
    if (l > r) break;
    while (d[r].x < x) r--;
    double ly = ((double)d[l].y - d[l - 1].y) / (d[l].x - d[l - 1].x) *
                    (x - d[l - 1].x) +
                d[l - 1].y;
    double ry = ((double)d[r].y - d[r + 1].y) / (d[r].x - d[r + 1].x) *
                    (x - d[r + 1].x) +
                d[r + 1].y;
    if (ly > ry) swap(ly, ry);
    ans += s2 * (floor(ry + eps) - ceil(ly - eps) + 1);
    s0 += floor(ry + eps) - ceil(ly - eps) + 1;
    s1 += s0;
    s2 += s1 * 2 - s0;
  }
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) scanf("%d%d", &d[i].x, &d[i].y);
  Work();
  for (int i = 1; i <= n; i++) d[i].x = -d[i].x;
  Work();
  for (int i = 1; i <= n; i++) swap(d[i].x, d[i].y);
  Work();
  for (int i = 1; i <= n; i++) d[i].x = -d[i].x;
  Work();
  printf("%.20Lf\n", (double)(ans * 0.5 / (s0 * s0 - s0)));
}