Geometry

// #define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;

#define P pair
typedef P < int, int > Pii;
typedef P < ll, ll > Pll;
typedef P < string, string > Pss;



#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()


#define forn(i, n) for(int (i) = 0; (i) < (n); (i)++)
#define fore(i, a) for(auto (i) : (a))

#define add_fill(a, c) setw(a) << setfill(c)
// #define endl '\n'

#define slimming(a) a.shrink_to_fit()
#define len(a) (ll)a.size()
#define check(a) next_permutation(all(a))

#define f first
#define s second

// #define ff f.f
// #define fs f.s
// #define sf s.f
// #define ss s.s

#define INF 1e9
#define MOD (ll)1e9

#define yes "YES"
#define no "NO"


#define pb push_back
#define eb emplace_back

// #define M_PI 3.14159265359

// ||           ----   ||
// ||          /    \  ||
// ||          |    |  ||
// ||          |    |  ||
// ||          |    |  ||
// ||          |    |  ||
// ||_______   |    |  ||_______
// \\_______|  \____/  \\_______|

#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,popcnt,abm,mmx,tune=native")
#pragma GCC optimize("fast-math")
#pragma GCC optimize "-O3"

struct Point{
    ld x, y;
    Point(){}
    Point(ld a, ld b){
        this->x = a;
        this->y = b;
    }
};

struct Vector{
    ld x, y;
    ld length2, length;
    Point bg, en;
    Vector(ld x, ld y){
        this->x = x;
        this->y = y;

        this->length2 = x * x + y * y;
        this->length = sqrt(this->length2);
    }

    Vector(Point a){
        this->x = a.x;
        this->y = a.y;

        this->length2 = a.x * a.x + a.y * a.y;
        this->length = sqrt(this->length2);
    }

    Vector(Point a, Point b){
        this->x = b.x - a.x;
        this->y = b.y - a.y;

        this->bg = a;
        this->en = b;

        this->length2 = this->x * this->x + this->y * this->y;
        this->length = sqrt(this->length2);
    }
};

struct Line{
    ld a, b, c;

    Line(){}

    Line(ll a, ll b, ll c){
        this->a = a;
        this->b = b;
        this->c = c;
    }

    Line(Point x, Point y){
        this->a = x.y - y.y;
        this->b = y.x - x.x;
        this->c = -a * x.x - b * x.y;
    }

    Line(Point x, Vector y){
        this->a = y.x;
        this->b = y.y;
        this->c = -a*x.x - b*x.y;
    }

    bool CheckPoint(Point q){
        // cout << (a*q.y + b*q.x + c) << ' ' << q.y;
        return (a*q.x + b*q.y + c == 0);
    }

    ll lol(Point q){
        return a*q.x + b*q.y + c;
    }

    Vector lineToVector(){
        Point q(1, (a + c)/b);
        Point w(2, (2*a + c)/b);
        return Vector(q, w);
    }
};

Vector operator+(Vector a, Vector b){return Vector(a.x + b.x, a.y + b.y);}
Vector operator*(Vector a, ll k){return Vector(a.x * k, a.y * k);}
ld DotProduct(Vector a, Vector b){return b.x * a.x + b.y * a.y;}
ld CrossProduct(Vector a, Vector b){return a.x * b.y - a.y * b.x;}
ld AngleRad(Vector a, Vector b){return -atan2(CrossProduct(a, b), DotProduct(a, b));}
ld PolarAngle(ld angle){
    if(angle >= 0)
        return angle;
    return (2*M_PI + angle);}

Point ReadPoint(){
    Point a;
    cin >> a.x >> a.y;
    return a;}
Line ReadLine(){
    ll a, b, c;
    cin >> a >> b >> c;
    return Line(a, b, c);}

ld dist(Point a, Point b){return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));}

void solve(){

}

int main() {
    // ios_base::sync_with_stdio(false);
    // cin.tie(nullptr);
    // cout.tie(nullptr);

    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);

    solve();
    return 0;
}