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, X[100006], Y[100006];
vector<vector<pair<int, int> > > H;
void solve() {
  int i, j, k, l, r, x, y;
  string s;
  H.resize(2000005);
  cin >> N;
  for (i = 0; i < N; i++) cin >> X[i] >> Y[i], X[i] += 1000000, Y[i] += 1000000;
  double ret = 0;
  double T;
  for (k = 0; k < 2; k++) {
    T = 0;
    for (x = 0; x < 2000001; x++) H[x].clear();
    for (i = 0; i < N; i++) {
      H[X[i]].push_back(make_pair(Y[i], Y[i]));
      if (X[i] != X[(i + 1) % N]) {
        int dx = (X[i] < X[(i + 1) % N]) ? 1 : -1;
        for (x = X[i] + dx; x != X[(i + 1) % N]; x += dx) {
          signed long long dy = 1LL * (x - X[i]) * (Y[(i + 1) % N] - Y[i]);
          signed long long y2 = Y[i] + dy / (X[(i + 1) % N] - X[i]);
          if ((dy >= 0) ^ (X[(i + 1) % N] < X[i]))
            H[x].push_back(
                make_pair(y2, y2 + ((dy % (X[(i + 1) % N] - X[i]) != 0))));
          else
            H[x].push_back(
                make_pair(y2 - (dy % (X[(i + 1) % N] - X[i]) != 0), y2));
        }
      }
    }
    double S1 = 0, S2 = 0;
    for (x = 0; x < 2000001; x++)
      if (H[x].size()) {
        int mf = H[x][0].first, ms = H[x][0].second;
        for (i = 0; i < H[x].size(); i++)
          mf = max(mf, H[x][i].first), ms = min(ms, H[x][i].second);
        int h = mf - ms + 1;
        if (h <= 0) continue;
        ret += h * (T * x * x - 2LL * x * S1 + S2);
        T += h;
        S1 += 1LL * h * x;
        S2 += 1LL * h * x * x;
      }
    for (i = 0; i < N; i++) swap(X[i], Y[i]);
  }
  (void)printf("%.12lf\n", ret / (T - 1.0) / T);
}
int main(int argc, char** argv) {
  string s;
  int i;
  if (argc == 1) ios::sync_with_stdio(false);
  for (i = 0; i < argc - 1; i++) s += argv[i + 1], s += '\n';
  for (i = 0; i < s.size(); i++) ungetc(s[s.size() - 1 - i], stdin);
  solve();
  return 0;
}