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 N;
long long x[100000];
long long y[100000];
int cntx[3000000];
long long sm0[3000000];
double sm1[3000000];
double sm2[3000000];
double ans;
long long tot;
void addTop(int i, int i2, bool skipStart) {
  for (long long cx = x[i] + skipStart; cx <= x[i2]; cx++) {
    long long cy = (y[i] * (x[i2] - cx) + y[i2] * (cx - x[i])) / (x[i2] - x[i]);
    cntx[cx] += cy;
    tot += cy;
  }
}
void removeBottom(int i, int i2, bool skipStart) {
  for (long long cx = x[i] + skipStart; cx <= x[i2]; cx++) {
    long long cy = (y[i] * (x[i2] - cx) + y[i2] * (cx - x[i])) / (x[i2] - x[i]);
    if (cy * (x[i2] - x[i]) == (y[i] * (x[i2] - cx) + y[i2] * (cx - x[i])))
      cy--;
    cntx[cx] -= cy;
    tot -= cy;
  }
}
void run() {
  for (int i = 0; i <= 2000005; i++) cntx[i] = 0;
  tot = 0;
  int j = 0;
  while (1) {
    if (x[(j + 1) % N] < x[j])
      j = (j + 1) % N;
    else if (x[(j + N - 1) % N] < x[j])
      j = (j + N - 1) % N;
    else
      break;
  }
  if (y[(j + 1) % N] > y[(j + N - 1) % N]) {
    bool skip = 0;
    for (int i = j; x[(i + 1) % N] >= x[i]; i = (i + 1) % N)
      if (x[(i + 1) % N] > x[i]) {
        addTop(i, (i + 1) % N, skip);
        skip = 1;
      }
    skip = 0;
    for (int i = j; x[(i + N - 1) % N] >= x[i]; i = (i + N - 1) % N)
      if (x[(i + N - 1) % N] > x[i]) {
        removeBottom(i, (i + N - 1) % N, skip);
        skip = 1;
      }
  } else {
    bool skip = 0;
    for (int i = j; x[(i + 1) % N] >= x[i]; i = (i + 1) % N)
      if (x[(i + 1) % N] > x[i]) {
        removeBottom(i, (i + 1) % N, skip);
        skip = 1;
      }
    skip = 0;
    for (int i = j; x[(i + N - 1) % N] >= x[i]; i = (i + N - 1) % N)
      if (x[(i + N - 1) % N] > x[i]) {
        addTop(i, (i + N - 1) % N, skip);
        skip = 1;
      }
  }
  for (int i = 1; i <= 2000005; i++) {
    sm0[i] = sm0[i - 1] + cntx[i];
    double csm0 = sm0[i - 1] + cntx[i] / 2.0;
    csm0 /= tot;
    csm0 /= (tot - 1);
    sm1[i] = sm1[i - 1] + csm0;
    sm2[i] = sm2[i - 1] + sm1[i];
    ans += cntx[i] * sm2[i - 1];
  }
}
int main() {
  cin >> N;
  for (int i = 0; i < N; i++) {
    cin >> x[i] >> y[i];
    x[i] += 1000001, y[i] += 1000001;
  }
  run();
  for (int i = 0; i < N; i++) swap(x[i], y[i]);
  run();
  cout << setprecision(20) << 2.0 * ans << '\n';
}