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;
int x[2100000], y[2100000], n, Min[2100000], Max[2100000];
long long s[2100000];
double ans = 0, p[2100000], sum1[2100000], sum2[2100000];
void solved() {
  int m = 0;
  for (int i = 1; i <= n; i++) m = max(m, x[i]);
  x[n + 1] = x[1];
  y[n + 1] = y[1];
  for (int i = 1; i <= m; i++) Min[i] = 1000000000, Max[i] = 0;
  for (int i = 1; i <= n; i++) {
    int t1 = x[i], t2 = x[i + 1], t3 = y[i], t4 = y[i + 1];
    if (t1 > t2) swap(t1, t2), swap(t3, t4);
    if (t1 == t2) {
      Min[t1] = min(Min[t1], t3);
      Max[t1] = max(Max[t1], t3);
      Min[t1] = min(Min[t1], t4);
      Max[t1] = max(Max[t1], t4);
      continue;
    }
    for (int j = t1; j <= t2; j++) {
      double y =
          (double)(t2 - j) * t3 / (t2 - t1) + (double)(j - t1) * t4 / (t2 - t1);
      Max[j] = max(Max[j], (int)floor(y + 1e-9));
      Min[j] = min(Min[j], (int)ceil(y - 1e-9));
    }
  }
  for (int i = 1; i <= m; i++) s[i] = Max[i] - Min[i] + 1 + s[i - 1];
  for (int i = 1; i <= m; i++) {
    p[i] = (double)(s[i] - s[i - 1]) / (s[m] - 1);
    sum1[i] = p[i] * i;
    sum2[i] = p[i] * i * i;
    sum1[i] += sum1[i - 1];
    sum2[i] += sum2[i - 1];
    p[i] += p[i - 1];
  }
  for (int i = 1; i <= m; i++) {
    double pp = (double)(s[i] - s[i - 1]) / s[m];
    ans += pp * i * i * (p[i - 1] + p[m] - p[i]) +
           (sum2[m] - sum2[i] + sum2[i - 1]) * pp -
           2 * (sum1[m] - sum1[i] + sum1[i - 1]) * i * pp;
  }
}
int main() {
  scanf("%d", &n);
  int minx = 1000000000, miny = 1000000000;
  for (int i = 1; i <= n; i++) {
    scanf("%d%d", &x[i], &y[i]);
    minx = min(minx, x[i]);
    miny = min(miny, y[i]);
  }
  minx--;
  miny--;
  for (int i = 1; i <= n; i++) x[i] -= minx, y[i] -= miny;
  solved();
  for (int i = 1; i <= n; i++) swap(x[i], y[i]);
  solved();
  printf("%.8lf\n", ans / 2);
  return 0;
}