/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author aryssoncf
 */



// Taken from: https://github.com/bqi343/USACO/blob/master/Implementations/content/contest/templateShort.cpp

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<ull> vul;
typedef vector<ll> vl;
typedef vector<pii> vpii;

#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define F0R(i, a) FOR(i,0,a)
#define ROF(i, a, b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i, a) ROF(i,0,a)
#define trav(a, x) for (auto& a: x)

#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define rsz resize

#define mp make_pair
#define pb push_back
#define f first
#define s second

const int MOD = 1e9 + 7; // 998244353; // = (119<<23)+1
const int MX = 2e5 + 5;

template<class T>
bool ckmin(T &a, const T &b) {
    return a > b ? a = b, 1 : 0;
}

template<class T>
bool ckmax(T &a, const T &b) {
    return a < b ? a = b, 1 : 0;
}

mt19937 rng((uint32_t) chrono::steady_clock::now().time_since_epoch().count());


//
// Created by aryssoncf on 28/10/2019.
//

#include <type_traits>


#include <iterator>
#include <utility>

template<typename T>
constexpr auto hasBegin(int) -> decltype(std::begin(std::declval<T>()), true) {
    return true;
}

constexpr bool hasBegin(...) {
    return false;
}

template<typename T>
using IsContainer = std::integral_constant<bool, hasBegin<T>(0)>;


#ifndef JHELPER_EXAMPLE_PROJECT_IO_HPP
#define JHELPER_EXAMPLE_PROJECT_IO_HPP

#endif //JHELPER_EXAMPLE_PROJECT_IO_HPP

template<typename T>
std::istream &operator>>(std::istream &is, std::vector<T> &vec) {
    for (T &element: vec) {
        is >> element;
    }
    return is;
}

template<typename T, typename U>
std::istream &operator>>(std::istream &is, std::pair<T, U> &p) {
    is >> p.first;
    is >> p.second;
    return is;
}

template<class X, class Y>
std::ostream &operator<<(std::ostream &os, std::pair<X, Y> const &p) {
    return os << p.first << " " << p.second;
}

template<class Ch, class Tr, class Container>
std::basic_ostream<Ch, Tr> &operator<<(std::basic_ostream<Ch, Tr> &os, Container const &x) {
    bool first = true;
    for (auto &y : x) {
        if (first) {
            first = false;
        } else {
            os << " ";
        }
        os << y;
    }
    return os;
}


using namespace std;

const double pi = 2 * acos(0.0);

typedef double T;

template<typename T>
int sgn(T x) {
    return (T(0) < x) - (x < T(0));
}

struct pt {
    T x, y;

    pt(T x = 0, T y = 0) : x(x), y(y) {}

    pt operator+(pt p) { return {x + p.x, y + p.y}; }

    pt operator-(pt p) { return {x - p.x, y - p.y}; }

    pt operator*(T d) { return {x * d, y * d}; }

    pt operator/(T d) { return {x / d, y / d}; } // only for floating point
};

bool operator==(pt a, pt b) { return a.x == b.x && a.y == b.y; }

bool operator!=(pt a, pt b) { return !(a == b); }

T sq(pt p) { return p.x * p.x + p.y * p.y; }

double abs(pt p) { return sqrt(sq(p)); }

double dist(pt p1, pt p2) {
    return abs(p1 - p2);
}

T sqDist(pt p1, pt p2) {
    return sq(p1 - p2);
}

double arg(pt p) { return atan2(p.y, p.x); }

ostream &operator<<(ostream &os, pt p) {
    return os << "(" << p.x << "," << p.y << ")";
}

pt translate(pt v, pt p) { return p + v; }

pt scale(pt c, double factor, pt p) {
    return c + (p - c) * factor;
}

pt rot(pt p, double a) {
    return {p.x * cos(a) - p.y * sin(a), p.x * sin(a) + p.y * cos(a)};
}

pt perp(pt p) { return {-p.y, p.x}; }

T dot(pt v, pt w) { return v.x * w.x + v.y * w.y; }

bool isPerp(pt v, pt w) { return dot(v, w) == 0; }

double angle(pt v, pt w) {
    double cosTheta = dot(v, w) / abs(v) / abs(w);
    return acos(max(-1.0, min(1.0, cosTheta)));
}

T cross(pt v, pt w) { return v.x * w.y - v.y * w.x; }

T orient(pt a, pt b, pt c) { return cross(b - a, c - a); }

// Works only if a, b, and c aren't collinear
bool inAngle(pt a, pt b, pt c, pt p) {
    assert(orient(a, b, c) != 0);
    if (orient(a, b, c) < 0) swap(b, c);
    return orient(a, b, p) >= 0 && orient(a, c, p) <= 0;
}

double orientedAngle(pt a, pt b, pt c) {
    if (orient(a, b, c) >= 0)
        return angle(b - a, c - a);
    else
        return 2 * pi - angle(b - a, c - a);
}

bool isConvex(vector<pt> p) {
    bool hasPos = false, hasNeg = false;
    for (int i = 0, n = p.size(); i < n; i++) {
        int o = orient(p[i], p[(i + 1) % n], p[(i + 2) % n]);
        if (o > 0) hasPos = true;
        if (o < 0) hasNeg = true;
    }
    return !(hasPos && hasNeg);
}

bool half(pt p, pt v = {1, 0}) {
    return cross(v, p) < 0 || (cross(v, p) == 0 && dot(v, p) < 0);
}

void polarSort(vector<pt> &v) {
    sort(v.begin(), v.end(), [](pt v, pt w) {
        return make_tuple(half(v), 0, sq(v)) < make_tuple(half(w), cross(v, w), sq(w));
    });
}

void polarSortAround(pt o, vector<pt> &v) {
    sort(v.begin(), v.end(), [&](pt v, pt w) {
        return make_tuple(half(v - o), 0) < make_tuple(half(w - o), cross(v - o, w - o));
    });
}

pt linearTransfo(pt p, pt q, pt r, pt fp, pt fq) {
    pt pq = q - p, num{cross(pq, fq - fp), dot(pq, fq - fp)};
    return fp + pt{cross(r - p, num), dot(r - p, num)} / sq(pq);
}

struct line {
    pt v;
    T c;

    // From direction vector v and offset c
    line(pt v, T c) : v(v), c(c) {}

    // From equation ax+by=c
    line(T a = 0, T b = 0, T c = 0) : v({b, -a}), c(c) {}

    // From points P and Q
    line(pt p, pt q) : v(q - p), c(cross(v, p)) {}

    // - these work with T = int
    T side(pt p) { return cross(v, p) - c; }

    double dist(pt p) { return abs(side(p)) / abs(v); }

    double sqDist(pt p) { return side(p) * side(p) / (double) sq(v); }

    line perpThrough(pt p) { return {p, p + perp(v)}; }

    bool cmpProj(pt p, pt q) {
        return dot(v, p) < dot(v, q);
    }

    line translate(pt t) { return {v, c + cross(v, t)}; }

    // - these require T = double
    line shiftLeft(double dist) { return {v, c + dist * abs(v)}; }

    pt proj(pt p) { return p - perp(v) * side(p) / sq(v); }

    pt refl(pt p) { return p - perp(v) * 2 * side(p) / sq(v); }
};

bool inter(line l1, line l2, pt &out) {
    T d = cross(l1.v, l2.v);
    if (d == 0) return false;
    out = (l2.v * l1.c - l1.v * l2.c) / d; // requires floating-point coordinates
    return true;
}

line bisector(line l1, line l2, bool interior) {
    assert(cross(l1.v, l2.v) != 0); // l1 and l2 cannot be parallel!
    double sign = interior ? 1 : -1;
    return {l2.v / abs(l2.v) + l1.v / abs(l1.v) * sign, l2.c / abs(l2.v) + l1.c / abs(l1.v) * sign};
}

bool inDisk(pt a, pt b, pt p) {
    return dot(a - p, b - p) <= 0;
}

bool onSegment(pt a, pt b, pt p) {
    return orient(a, b, p) == 0 && inDisk(a, b, p);
}

bool properInter(pt a, pt b, pt c, pt d, pt &out) {
    double oa = orient(c, d, a), ob = orient(c, d, b), oc = orient(a, b, c), od = orient(a, b, d);
    // Proper intersection exists iff opposite signs
    if (oa * ob < 0 && oc * od < 0) {
        out = (a * ob - b * oa) / (ob - oa);
        return true;
    }
    return false;
}

// To create sets of points we need a comparison function
struct cmpX {
    bool operator()(pt a, pt b) {
        return make_pair(a.x, a.y) < make_pair(b.x, b.y);
    }
};

set<pt, cmpX> inters(pt a, pt b, pt c, pt d) {
    pt out;
    if (properInter(a, b, c, d, out)) return {out};
    set<pt, cmpX> s;
    if (onSegment(c, d, a)) s.insert(a);
    if (onSegment(c, d, b)) s.insert(b);
    if (onSegment(a, b, c)) s.insert(c);
    if (onSegment(a, b, d)) s.insert(d);
    return s;
}

double segPoint(pt a, pt b, pt p) {
    if (a != b) {
        line l(a, b);
        if (l.cmpProj(a, p) && l.cmpProj(p, b)) // if closest to projection
            return l.dist(p); // output distance to line
    }
    return min(abs(p - a), abs(p - b)); // otherwise distance to A or B
}

pt closest(pt a, pt b, pt p) {
    if (a != b) {
        line l(a, b);
        if (l.cmpProj(a, p) && l.cmpProj(p, b)) {
            return l.proj(p);
        }
    }
    return abs(p - a) <= abs(p - b) ? a : b;
}

double segSeg(pt a, pt b, pt c, pt d) {
    pt dummy;
    if (properInter(a, b, c, d, dummy))
        return 0;
    return min({segPoint(a, b, c), segPoint(a, b, d), segPoint(c, d, a), segPoint(c, d, b)});
}

double areaTriangle(pt a, pt b, pt c) {
    return abs(cross(b - a, c - a)) / 2.0;
}

double areaPolygon(vector<pt> p) {
    double area = 0.0;
    for (int i = 0, n = p.size(); i < n; i++) {
        area += cross(p[i], p[(i + 1) % n]); // wrap back to 0 if i == n-1
    }
    return abs(area) / 2.0;
}

// true if P at least as high as A (blue part)
bool above(pt a, pt p) {
    return p.y >= a.y;
}

// check if [PQ] crosses ray from A
bool crossesRay(pt a, pt p, pt q) {
    return (above(a, q) - above(a, p)) * orient(a, p, q) > 0;
}

// if strict, returns false when A is on the boundary
bool inPolygon(vector<pt> p, pt a, bool strict = true) {
    int numCrossings = 0;
    for (int i = 0, n = p.size(); i < n; i++) {
        if (onSegment(p[i], p[(i + 1) % n], a))
            return !strict;
        numCrossings += crossesRay(a, p[i], p[(i + 1) % n]);
    }
    return numCrossings & 1; // inside if odd number of crossings
}

double angleTravelled(pt a, pt p, pt q) {
    // remainder ensures the value is in [-pi,pi]
    return remainder(arg(q - a) - arg(p - a), 2 * pi);
}

struct Angle {
    pt d;
    int t = 0; // direction and number of full turns
    Angle t180() { return {d * (-1), t + half(d)}; }

    Angle t360() { return {d, t + 1}; }
};

bool operator<(Angle a, Angle b) {
    return make_tuple(a.t, half(a.d), 0) < make_tuple(b.t, half(b.d), cross(a.d, b.d));
}

Angle moveTo(Angle a, pt newD) {
    // check that segment [DD’] doesn’t go through the origin
    assert(!onSegment(a.d, newD, {0, 0}));
    Angle b{newD, a.t};
    if (a.t180() < b) // if b more than half a turn bigger
        b.t--; // decrease b by a full turn
    if (b.t180() < a) // if b more than half a turn smaller
        b.t++; // increase b by a full turn
    return b;
}

int windingNumber(vector<pt> p, pt o) {
    Angle a{p.back() - o}; // start at last vertex
    for (pt d : p)
        a = moveTo(a, d - o); // move to first vertex, second, etc.
    return a.t;
}

pt circumCenter(pt a, pt b, pt c) {
    b = b - a, c = c - a; // consider coordinates relative to A
    assert(cross(b, c) != 0); // no circumcircle if A,B,C aligned
    return a + perp(b * sq(c) - c * sq(b)) / cross(b, c) / 2;
}

bool inCircle(pt o, double r, pt p, bool includeBorder = true) {
    return sgn(sqDist(o, p) - r * r) < (int) includeBorder;
}

int circleLine(pt o, double r, line l, pair<pt, pt> &out) {
    double h2 = r * r - l.sqDist(o);
    if (h2 >= 0) { // the line touches the circle
        pt p = l.proj(o); // point P
        pt h = l.v * sqrt(h2) / abs(l.v); // vector parallel to l, of length h
        out = {p - h, p + h};
    }
    return 1 + sgn(h2);
}

int circleCircle(pt o1, double r1, pt o2, double r2, pair<pt, pt> &out) {
    pt d = o2 - o1;
    double d2 = sq(d);
    if (d2 == 0) {
        assert(r1 != r2);
        return 0;
    } // concentric circles
    double pd = (d2 + r1 * r1 - r2 * r2) / 2; // = |O_1P| * d
    double h2 = r1 * r1 - pd * pd / d2; // = hˆ2
    if (h2 >= 0) {
        pt p = o1 + d * pd / d2, h = perp(d) * sqrt(h2 / d2);
        out = {p - h, p + h};
    }
    return 1 + sgn(h2);
}

int tangents(pt o, double r, pt p, pair<pt, pt> &out) {
    double r2 = sqDist(o, p) - r * r;
    if (r2 >= 0) {
        double r1 = sqrt(r2);
        return circleCircle(o, r, p, r1, out);
    }
    return 1 + sgn(r2);
}

int tangents(pt o1, double r1, pt o2, double r2, bool inner, vector<
        pair<pt, pt>> &out) {
    if (inner) r2 = -r2;
    pt d = o2 - o1;
    double dr = r1 - r2, d2 = sq(d), h2 = d2 - dr * dr;
    if (d2 == 0 || h2 < 0) {
        assert(h2 != 0);
        return 0;
    }
    for (double sign : {-1, 1}) {
        pt v = (d * dr + perp(d) * sqrt(h2) * sign) / d2;
        out.push_back({o1 + v * r1, o2 + v * r2});
    }
    return 1 + (h2 > 0);
}

struct p3 {
    T x, y, z;

    // Basic vector operations
    p3 operator+(p3 p) { return {x + p.x, y + p.y, z + p.z}; }

    p3 operator-(p3 p) { return {x - p.x, y - p.y, z - p.z}; }

    p3 operator*(T d) { return {x * d, y * d, z * d}; }

    p3 operator/(T d) { return {x / d, y / d, z / d}; } // only for floating-point
    // Some comparators
    bool operator==(p3 p) { return tie(x, y, z) == tie(p.x, p.y, p.z); }

    bool operator!=(p3 p) { return !operator==(p); }
};

p3 zero{0, 0, 0};

T operator|(p3 v, p3 w) { return v.x * w.x + v.y * w.y + v.z * w.z; }

T sq(p3 v) { return v | v; }

double abs(p3 v) { return sqrt(sq(v)); }

p3 unit(p3 v) { return v / abs(v); }

double angle(p3 v, p3 w) {
    double cosTheta = (v | w) / abs(v) / abs(w);
    return acos(max(-1.0, min(1.0, cosTheta)));
}

p3 operator*(p3 v, p3 w) {
    return {v.y * w.z - v.z * w.y, v.z * w.x - v.x * w.z, v.x * w.y - v.y * w.x};
}

T orient(p3 p, p3 q, p3 r, p3 s) { return (q - p) * (r - p) | (s - p); }

T orientByNormal(p3 p, p3 q, p3 r, p3 n) { return (q - p) * (r - p) | n; }

struct plane {
    p3 n;
    T d;

    // From normal n and offset d
    plane(p3 n, T d) : n(n), d(d) {}

    // From normal n and point P
    plane(p3 n, p3 p) : n(n), d(n | p) {}

    // From three non-collinear points P,Q,R
    plane(p3 p, p3 q, p3 r) : plane((q - p) * (r - p), p) {}

    // - these work with T = int
    T side(p3 p) { return (n | p) - d; }

    double dist(p3 p) { return abs(side(p)) / abs(n); }

    plane translate(p3 t) { return {n, d + (n | t)}; }

    // - these require T = double
    plane shiftUp(double dist) { return {n, d + dist * abs(n)}; }

    p3 proj(p3 p) { return p - n * side(p) / sq(n); }

    p3 refl(p3 p) { return p - n * 2 * side(p) / sq(n); }
};

struct coords {
    p3 o, dx, dy, dz;

    // From three points P,Q,R on the plane:
    // build an orthonormal 3D basis
    coords(p3 p, p3 q, p3 r) : o(p) {
        dx = unit(q - p);
        dz = unit(dx * (r - p));
        dy = dz * dx;
    }

    // From four points P,Q,R,S:
    // take directions PQ, PR, PS as is
    coords(p3 p, p3 q, p3 r, p3 s) : o(p), dx(q - p), dy(r - p), dz(s - p) {}

    pt pos2d(p3 p) { return {(p - o) | dx, (p - o) | dy}; }

    p3 pos3d(p3 p) { return {(p - o) | dx, (p - o) | dy, (p - o) | dz}; }
};

struct line3d {
    p3 d, o;

    // From two points P, Q
    line3d(p3 p, p3 q) : d(q - p), o(p) {}

    // From two planes p1, p2 (requires T = double)
    line3d(plane p1, plane p2) {
        d = p1.n * p2.n;
        o = (p2.n * p1.d - p1.n * p2.d) * d / sq(d);
    }

    // - these work with T = int
    double sqDist(p3 p) { return sq(d * (p - o)) / sq(d); }

    double dist(p3 p) { return sqrt(sqDist(p)); }

    bool cmpProj(p3 p, p3 q) { return (d | p) < (d | q); }

    // - these require T = double
    p3 proj(p3 p) { return o + d * (d | (p - o)) / sq(d); }

    p3 refl(p3 p) { return proj(p) * 2 - p; }

    p3 inter(plane p) { return o - d * p.side(o) / (p.n | d); }
};

double dist(line3d l1, line3d l2) {
    p3 n = l1.d * l2.d;
    if (n == zero) // parallel
        return l1.dist(l2.o);
    return abs((l2.o - l1.o) | n) / abs(n);
}

p3 closestOnL1(line3d l1, line3d l2) {
    p3 n2 = l2.d * (l1.d * l2.d);
    return l1.o + l1.d * ((l2.o - l1.o) | n2) / (l1.d | n2);
}

double smallAngle(p3 v, p3 w) {
    return acos(min(abs(v | w) / abs(v) / abs(w), 1.0));
}

double angle(plane p1, plane p2) {
    return smallAngle(p1.n, p2.n);
}

bool isParallel(plane p1, plane p2) {
    return p1.n * p2.n == zero;
}

bool isPerpendicular(plane p1, plane p2) {
    return (p1.n | p2.n) == 0;
}

double angle(line3d l1, line3d l2) {
    return smallAngle(l1.d, l2.d);
}

bool isParallel(line3d l1, line3d l2) {
    return l1.d * l2.d == zero;
}

bool isPerpendicular(line3d l1, line3d l2) {
    return (l1.d | l2.d) == 0;
}

double angle(plane p, line3d l) {
    return pi / 2 - smallAngle(p.n, l.d);
}

bool isParallel(plane p, line3d l) {
    return (p.n | l.d) == 0;
}

bool isPerpendicular(plane p, line3d l) {
    return p.n * l.d == zero;
}

line3d perpThrough(plane p, p3 o) { return line3d(o, o + p.n); }

plane perpThrough(line3d l, p3 o) { return plane(l.d, o); }

p3 vectorArea2(vector<p3> p) { // vector area * 2 (to avoid divisions)
    p3 S = zero;
    for (int i = 0, n = p.size(); i < n; i++)
        S = S + p[i] * p[(i + 1) % n];
    return S;
}

double area(vector<p3> p) {
    return abs(vectorArea2(p)) / 2.0;
}

// Create arbitrary comparator for map<>
bool operator<(p3 p, p3 q) {
    return tie(p.x, p.y, p.z) < tie(q.x, q.y, q.z);
}

struct edge {
    int v;
    bool same; // = is the common edge in the same order?
};

// Given a series of faces (lists of points), reverse some of them
// so that their orientations are consistent
void reorient(vector<vector<p3>> &fs) {
    int n = fs.size();
    // Find the common edges and create the resulting graph
    vector<vector<edge>> g(n);
    map<pair<p3, p3>, int> es;
    for (int u = 0; u < n; u++) {
        for (int i = 0, m = fs[u].size(); i < m; i++) {
            p3 a = fs[u][i], b = fs[u][(i + 1) % m];
            // Let’s look at edge [AB]
            if (es.count({a, b})) { // seen in same order
                int v = es[{a, b}];
                g[u].push_back({v, true});
                g[v].push_back({u, true});
            } else if (es.count({b, a})) { // seen in different order
                int v = es[{b, a}];
                g[u].push_back({v, false});
                g[v].push_back({u, false});
            } else { // not seen yet
                es[{a, b}] = u;
            }
        }
    }
    // Perform BFS to find which faces should be flipped
    vector<bool> vis(n, false), flip(n);
    flip[0] = false;
    queue<int> q;
    q.push(0);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (edge e : g[u]) {
            if (!vis[e.v]) {
                vis[e.v] = true;
                // If the edge was in the same order,
                // exactly one of the two should be flipped
                flip[e.v] = (flip[u] ^ e.same);
                q.push(e.v);
            }
        }
    }
    // Actually perform the flips
    for (int u = 0; u < n; u++)
        if (flip[u])
            reverse(fs[u].begin(), fs[u].end());
}

double volume(vector<vector<p3>> fs) {
    double vol6 = 0.0;
    for (vector<p3> f : fs)
        vol6 += (vectorArea2(f) | f[0]);
    return abs(vol6) / 6.0;
}

p3 sph(double r, double lat, double lon) {
    lat *= M_PI / 180, lon *= M_PI / 180;
    return {r * cos(lat) * cos(lon), r * cos(lat) * sin(lon), r * sin(lat)};
}

int sphereLine(p3 o, double r, line3d l, pair<p3, p3> &out) {
    double h2 = r * r - l.sqDist(o);
    if (h2 < 0) return 0; // the line doesn’t touch the sphere
    p3 p = l.proj(o); // point P
    p3 h = l.d * sqrt(h2) / abs(l.d); // vector parallel to l, of length h
    out = {p - h, p + h};
    return 1 + (h2 > 0);
}

double greatCircleDist(p3 o, double r, p3 a, p3 b) {
    return r * angle(a - o, b - o);
}

bool validSegment(p3 a, p3 b) {
    return a * b != zero || (a | b) > 0;
}

bool properInter(p3 a, p3 b, p3 c, p3 d, p3 &out) {
    p3 ab = a * b, cd = c * d; // normals of planes OAB and OCD
    int oa = sgn(cd | a), ob = sgn(cd | b), oc = sgn(ab | c), od = sgn(ab | d);
    out = ab * cd * od; // four multiplications => careful with overflow!
    return (oa != ob && oc != od && oa != oc);
}

bool onSphSegment(p3 a, p3 b, p3 p) {
    p3 n = a * b;
    if (n == zero)
        return a * p == zero && (a | p) > 0;
    return (n | p) == 0 && (n | a * p) >= 0 && (n | b * p) <= 0;
}

struct directionSet : vector<p3> {
    using vector::vector; // import constructors
    void insert(p3 p) {
        for (p3 q : *this) if (p * q == zero) return;
        push_back(p);
    }
};

// Works only if (a,b) and (c,d) aren't pairs of opposite points in sphere surface!
directionSet intersSph(p3 a, p3 b, p3 c, p3 d) {
    assert(validSegment(a, b) && validSegment(c, d));
    p3 out;
    if (properInter(a, b, c, d, out)) return {out};
    directionSet s;
    if (onSphSegment(c, d, a)) s.insert(a);
    if (onSphSegment(c, d, b)) s.insert(b);
    if (onSphSegment(a, b, c)) s.insert(c);
    if (onSphSegment(a, b, d)) s.insert(d);
    return s;
}

double angleSph(p3 a, p3 b, p3 c) {
    return angle(a * b, a * c);
}

double orientedAngleSph(p3 a, p3 b, p3 c) {
    if ((a * b | c) >= 0)
        return angleSph(a, b, c);
    else
        return 2 * M_PI - angleSph(a, b, c);
}

double areaOnSphere(double r, vector<p3> p) {
    int n = p.size();
    double sum = -(n - 2) * M_PI;
    for (int i = 0; i < n; i++)
        sum += orientedAngleSph(p[(i + 1) % n], p[(i + 2) % n], p[i]);
    return r * r * sum;
}

int windingNumber3D(vector<vector<p3>> fs) {
    double sum = 0;
    for (vector<p3> f : fs)
        sum += remainder(areaOnSphere(1, f), 4 * M_PI);
    return round(sum / (4 * M_PI));
}

//int main() {
//    pt a{3,4}, b{2,-1};
//    cout << a+b << " " << a-b << "\n"; // (5,3) (1,5)
//    cout << a*-1 << " " << b/2 << "\n"; // (-3,-4) (1.5,2)
//    return 0;
//}


using namespace std;

class CAverageLength {
public:
    void solve(std::istream &in, std::ostream &out) {
        int n;
        in >> n;
        vector<pt> points(n);
        trav(p, points) {
            in >> p.x >> p.y;
        }
        vi id(n);
        iota(all(id), 0);
        sort(all(id));
        double sum = 0;
        int times = 0;
        do {
            times++;
            double d = 0;
            FOR(i, 1, n) {
                d += dist(points[id[i - 1]], points[id[i]]);
            }
            sum += d;
        } while (next_permutation(all(id)));
        double res = sum / times;
        out << fixed << setprecision(10) << res << '\n';
    }

    void setup() {}
};


int main() {
    std::ios_base::sync_with_stdio(false);
    CAverageLength solver;
    solver.setup();
    std::istream &in(std::cin);
    std::ostream &out(std::cout);
    in.tie(nullptr);
    out << std::fixed;
    out.precision(20);
    solver.solve(in, out);
    return 0;
}


Measured memory_bytes: 256