#include <bits/stdc++.h>

using namespace std;

#define sz(x) ((int) (x).size())
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define re return
#define endl '\n'

using ll = long long;
using ull = unsigned long long;
using ii = pair<int, int>;
using vi = vector<int>;
using vii = vector<ii>;
using ld = long double;

template <class T> T abs (T x) { re x > 0 ? x : -x; }
template <class T> T sqr (T x) { re x * x; }

const ld pi = 4 * atan(1.);
const int inf = 1e9 + 7;
const int N = 3e5 + 17;

const double eps = 1e-9;

bool Eq (double x, double y) {
	return abs(x - y) < eps;
}

bool Less (double x, double y) {
	return x < y && !Eq(x, y);
}

struct point {
 	double x, y;
 	point () : x(), y() {}
 	point (double _x, double _y) : x(_x), y(_y) {}
 	point operator+(const point& a) const {
 		return point(x + a.x, y + a.y);
 	}
 	point operator-(const point& a) const {
 		return point(x - a.x, y - a.y);
 	}
 	point operator*(double k) const {
 		return point(x * k, y * k);
 	}
 	point operator/(double k) const {
 		return point(x / k, y / k);
 	}
 	double operator*(const point& a) const {
 		return x * a.y - y * a.x;
 	}
 	double operator%(const point& a) const {
    	return x * a.x + y * a.y;
	}
	bool operator==(const point& a) const {
		return Eq(x, a.x) && Eq(y, a.y);
	}
	bool operator<(const point& a) const {
		return Eq(x, a.x) ? Less(y, a.y) : x < a.x;
	}
	double sqrlen() const {
		return (*this) % (*this);
	}
	double len() const {
		return sqrt(sqrlen());
	}
	double sqrdist(const point& a) const {
		return (*this - a).sqrlen();
	}
	double dist(const point& a) const {
		return (*this - a).len();
	}
	point norm(double k = 1) const {
		return (*this) * (k / len());
	}
	point ort() const {
		return point(-y, x);
	}
	point rotate(double ang) {
		return (*this) * cos(ang) + ort() * sin(ang);
	}
};

ostream& operator<<(ostream& out, const point& x) {
    cout << "(" << x.x << ", " << x.y << ")";
    re out;
}

istream& operator>>(istream& in, point& x) {
	double a, b; cin >> a >> b;
	x = point(a, b);
    return in;
}

double getang (point a, point b) {
	return atan2(a * b, a % b);
}

bool online (point a, point b, point c) {
	return Eq(0, (a - b) * (a - c));
}

bool onseg (point a, point b, point x) {
	if (!online(a, b, x)) re false;
	return Eq(0, (x - a) % (x - b));
}

bool intersect (point A, point a, point B, point b, point& ans) {
	if (Eq(0, a * b)) return online(A, A + a, B);
	ans = B + b * (((A - B) * a) / (b * a));
	return true;
}

bool intersect (point a, point b, point c, point d) {
	if (Eq(0, (b - a) * (d - c))) {
		if (!online(a, b, c)) re false;
		auto x = b - a;
		auto l1 = a % x, r1 = b % x;
		if (Less(r1, l1)) swap(l1, r1);
		auto l2 = c % x, r2 = d % x;
		if (Less(r2, l2)) swap(l2, r2);
		return !Less(min(r1, r2), max(l1, l2));
	}
	auto sgn = [](double x) { return Eq(0, x) ? 0 : (x > 0 ? 1 : -1); };
	if (sgn((a - c) * (a - d)) * sgn((b - c) * (b - d)) == 1) re false;
	if (sgn((c - a) * (c - b)) * sgn((d - a) * (d - b)) == 1) re false;
	re true;
}

point project (point a, point v, point x) {
	return a + v.norm(((x - a) % v) / v.len());
}

bool intersect (point a, point v, point o, double r, point& ans1, point& ans2) {
	auto h = project(a, v, o);
	double d = (h - o).sqrlen();
	if (Eq(d, sqr(r))) { ans1 = ans2 = h; re true; }
	if (Less(sqr(r), d)) re false;
	double cur = sqrt(sqr(r) - d);
	ans1 = h + v.norm(cur);
	ans2 = h - v.norm(cur);
	re true;
}

bool inpoly (vector<point>& poly, point x) {
	double ang = 0;
	for (int i = 0; i < sz(poly); i++) {
		point l = poly[i], r = poly[(i + 1) % sz(poly)];
		if (online(l, r, x) && onseg(l, r, x)) re true;
		ang += getang(l - x, r - x);
	}
	return ang > 1;
}

double area (vector<point>& poly) {
	double ans = 0;
	for (int i = 0; i < sz(poly) - 1; i++)
		ans += poly[i] * poly[i + 1];
	return abs(ans + poly.back() * poly[0]) / 2;
}

vector<point> convex (vector<point>& a) {
	sort(all(a));
	vector<point> up, down;
	for (auto x : a) {
		while (sz(up) > 1 && !Less((up.back() - up[sz(up) - 2]) * (x - up.back()), 0)) up.pop_back();
		while (sz(down) > 1 && !Less(0, (down.back() - down[sz(down) - 2]) * (x - down.back()))) down.pop_back();
		up.pb(x), down.pb(x);
	}
	for (int i = 1; i < sz(down) - 1; i++) up.pb(down[i]);
	return up;
}

int main() {
	ios::sync_with_stdio();
	cin.tie(0); cout.tie(0);

}