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 int N = (int)1e5 + 5, X = (int)2e6 + 100;
int n, x[N], y[N], cnt[X];
long double work() {
  long double area = 0;
  for (int i = 0; i < n; i++) area += x[i + 1] * y[i] - x[i] * y[i + 1];
  if (area < 0) {
    reverse(x, x + n);
    x[n] = x[0];
    reverse(y, y + n);
    y[n] = y[0];
  }
  long long tot = 0;
  long double ans1 = 0, ans2 = 0;
  for (int i = 0; i < X; i++) cnt[i] = 0;
  for (int i = 0; i < n; i++) {
    if (x[i] < x[i + 1]) {
      for (int j = x[i]; j < x[i + 1]; j++)
        cnt[j] += floor(
            y[i] + 1. * (y[i + 1] - y[i]) / (x[i + 1] - x[i]) * (j - x[i]) +
            1e-8);
      if (x[i + 1] >= x[(i + 2) % n]) cnt[x[i + 1]] += y[i + 1];
    } else if (x[i] > x[i + 1]) {
      for (int j = x[i]; j > x[i + 1]; j--)
        cnt[j] -= floor(
            y[i] + 1. * (y[i + 1] - y[i]) / (x[i + 1] - x[i]) * (j - x[i]) -
            1e-8);
      if (x[i + 1] <= x[(i + 2) % n]) cnt[x[i + 1]] -= y[i + 1] - 1;
    }
  }
  for (int i = 0; i < X; i++) {
    tot += cnt[i];
    ans1 += 1. * i * cnt[i];
    ans2 += 1. * i * i * cnt[i];
  }
  return (ans2 * tot - 2 * ans1 * ans1 + ans2 * tot) / tot / (tot - 1);
}
int main() {
  scanf("%d", &n);
  for (int i = 0; i < n; i++)
    scanf("%d%d", &x[i], &y[i]), x[i] += X / 2, y[i] += X / 2;
  x[n] = x[0];
  y[n] = y[0];
  long double ans = work();
  for (int i = 0; i <= n; i++) swap(x[i], y[i]);
  ans += work();
  printf("%.12lf\n", double(ans / 2));
}