#include <bits/stdc++.h>
using namespace std;
#ifndef ONLINE_JUDGE
	#include <boost/multiprecision/cpp_int.hpp>
	#include <boost/multiprecision/cpp_dec_float.hpp>
	using bll = boost::multiprecision::cpp_int;
	using bdouble = boost::multiprecision::cpp_dec_float_100;
#endif
#ifdef LOCAL_DEV
	void debug_impl() { std::cerr << '\n'; }
	template<typename Head, typename... Tail> void debug_impl(Head head, Tail... tail) { std::cerr << " " << head << (sizeof...(tail) ? "," : ""); debug_impl(tail...); }
	#define debug(...) do { std::cerr << "(" << #__VA_ARGS__ << ") ="; debug_impl(__VA_ARGS__); } while (false)
#else
	#define debug(...) do {} while (false)
#endif
#ifdef LOCAL_TEST
	#define BOOST_STACKTRACE_USE_ADDR2LINE
	#define BOOST_STACKTRACE_ADDR2LINE_LOCATION /usr/local/opt/binutils/bin/addr2line
	#define _GNU_SOURCE
	#include <boost/stacktrace.hpp>
	namespace std {
		template<typename T> class dvector : public std::vector<T> {
		public:
			dvector() : std::vector<T>() {}
			explicit dvector(size_t n, const T& value = T()) : std::vector<T>(n, value) {}
			dvector(const std::vector<T>& v) : std::vector<T>(v) {}
			dvector(const std::initializer_list<T> il) : std::vector<T>(il) {}
			dvector(const std::string::iterator first, const std::string::iterator last) : std::vector<T>(first, last) {}
			dvector(const typename std::vector<T>::iterator first, const typename std::vector<T>::iterator last) : std::vector<T>(first, last) {}
			dvector(const typename std::vector<T>::reverse_iterator first, const typename std::vector<T>::reverse_iterator last) : std::vector<T>(first, last) {}
			dvector(const typename std::vector<T>::const_iterator first, const typename std::vector<T>::const_iterator last) : std::vector<T>(first, last) {}
			dvector(const typename std::vector<T>::const_reverse_iterator first, const typename std::vector<T>::const_reverse_iterator last) : std::vector<T>(first, last) {}
			T& operator[](size_t n) {
				try { return this->at(n); } catch (const std::exception& e) {
					std::cerr << boost::stacktrace::stacktrace() << '\n'; return this->at(n);
				}
			}
			const T& operator[](size_t n) const {
				try { return this->at(n); } catch (const std::exception& e) {
					std::cerr << boost::stacktrace::stacktrace() << '\n'; return this->at(n);
				}
			}
		};
	}
	class dbool {
	private:
		bool boolvalue;
	public:
		dbool() : boolvalue(false) {}
		dbool(bool b) : boolvalue(b) {}
		dbool(const dbool& b) : boolvalue(b.boolvalue) {}
		operator bool&() { return boolvalue; }
		operator const bool&() const { return boolvalue; }
	};
	template<typename T> std::ostream& operator<<(std::ostream& s, const std::dvector<T>& v) {
		for (size_t i = 0; i < v.size(); ++i){ s << v[i]; if (i < v.size() - 1) s << "\t"; } return s; }
	template<typename T> std::ostream& operator<<(std::ostream& s, const std::dvector<std::dvector<T>>& vv) {
		s << "\n"; for (size_t i = 0; i < vv.size(); ++i){ s << vv[i] << "\n"; } return s; }
	template<typename T> std::ostream& operator<<(std::ostream& s, const std::set<T>& se) {
		s << "{ "; for (auto itr = se.begin(); itr != se.end(); ++itr){ s << (*itr) << "\t"; } s << "}"; return s; }
	template<typename T> std::ostream& operator<<(std::ostream& s, const std::multiset<T>& se) {
		s << "{ "; for (auto itr = se.begin(); itr != se.end(); ++itr){ s << (*itr) << "\t"; } s << "}"; return s; }
	template <typename T, size_t N> std::ostream& operator<<(std::ostream& s, const std::array<T, N>& a) {
		s << "{ "; for (size_t i = 0; i < N; ++i){ s << a[i] << "\t"; } s << "}"; return s; }
	template<typename T1, typename T2> std::ostream& operator<<(std::ostream& s, const std::map<T1, T2>& m) {
		s << "{\n"; for (auto itr = m.begin(); itr != m.end(); ++itr){ s << "\t" << (*itr).first << " : " << (*itr).second << "\n"; } s << "}"; return s; }
	template<typename T1, typename T2> std::ostream& operator<<(std::ostream& s, const std::pair<T1, T2>& p) {
		return s << "(" << p.first << ", " << p.second << ")"; }
	#define vector dvector
	#define bool dbool
	class SIGFPE_exception : std::exception {};
	class SIGSEGV_exception : std::exception {};
	void catch_SIGFPE(int e) { std::cerr << boost::stacktrace::stacktrace() << '\n'; throw SIGFPE_exception();	}
	void catch_SIGSEGV(int e) { std::cerr << boost::stacktrace::stacktrace() << '\n'; throw SIGSEGV_exception(); }
	signed convertedmain();
	signed main() { signal(SIGFPE, catch_SIGFPE); signal(SIGSEGV, catch_SIGSEGV); return convertedmain(); }
	#define main() convertedmain()
#endif
//#define int long long
using ll = long long;
//constexpr int INF = 1e9;//INT_MAX=(1<<31)-1=2147483647
constexpr ll INF = (ll)1e18;//(1LL<<63)-1=9223372036854775807
constexpr ll MOD = (ll)1e9 + 7;
constexpr double EPS = 1e-9;
constexpr ll dx[4] = {1LL, 0LL, -1LL, 0LL};
constexpr ll dy[4] = {0LL, 1LL, 0LL, -1LL};
constexpr ll dx8[8] = {1LL, 0LL, -1LL, 0LL, 1LL, 1LL, -1LL, -1LL};
constexpr ll dy8[8] = {0LL, 1LL, 0LL, -1LL, 1LL, -1LL, 1LL, -1LL};
#define rep(i, n)   for(ll i=0, i##_length=(n); i< i##_length; ++i)
#define repeq(i, n) for(ll i=1, i##_length=(n); i<=i##_length; ++i)
#define rrep(i, n)   for(ll i=(n)-1; i>=0; --i)
#define rrepeq(i, n) for(ll i=(n)  ; i>=1; --i)
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
void p() { std::cout << '\n'; }
template<typename Head, typename... Tail> void p(Head head, Tail... tail) { std::cout << head << (sizeof...(tail) ? " " : ""); p(tail...); }
template<typename T> inline void pv(std::vector<T>& v) { for(ll i=0, N=v.size(); i<N; i++) std::cout << v[i] << " \n"[i==N-1]; }
template<typename T> inline T gcd(T a, T b) { return b ? gcd(b,a%b) : a; }
template<typename T> inline T lcm(T a, T b) { return a / gcd(a,  b) * b; }
template<typename T> inline bool chmax(T& a, T b) { return a < b && (a = b, true); }
template<typename T> inline bool chmin(T& a, T b) { return a > b && (a = b, true); }
template<typename T> inline void uniq(std::vector<T>& v) { v.erase(std::unique(v.begin(), v.end()), v.end()); }

/*-----8<-----template-----8<-----*/

//doubleにおける == 判定
inline double equals(double a,double b){ return std::abs(a-b)<EPS; }

//点、ベクトル
class Point {
public:
	double x,y;
	Point(double x=0., double y=0.) : x(x), y(y) {}
	Point operator + (Point p) {return Point(x+p.x, y+p.y);}
	Point operator - (Point p) {return Point(x-p.x, y-p.y);}
	Point operator * (Point p) {return Point(x*p.x, y*p.y);}
	Point operator / (Point p) {return Point(x/p.x, y/p.y);}
	Point operator + (double n) {return Point(x+n, y+n);}
	Point operator - (double n) {return Point(x-n, y-n);}
	Point operator * (double n) {return Point(x*n, y*n);}
	Point operator / (double n) {return Point(x/n, y/n);}

	double abs(){ return sqrt(norm()); }
	double norm(){ return x*x + y*y; }

	bool operator < (const Point &p) const {
		return std::abs(x-p.x)>EPS ? x<p.x : y<p.y;
	}
	bool operator > (const Point &p) const {
		return std::abs(x-p.x)>EPS ? x>p.x : y>p.y;
	}
	bool operator == (const Point &p) const {
		return std::abs(x-p.x)<EPS && std::abs(y-p.y)<EPS;
	}
	bool operator != (const Point &p) const {
		return !(*this==p);
	}
};
using Vector = Point;
std::ostream& operator<<(std::ostream& s, const Point& p) {
	return s << "(" << p.x << ", " << p.y << ")";
}

//線分、直線
class Segment {
public:
	Point p1,p2;
	Segment() {}
	Segment(Point p1, Point p2) : p1(p1), p2(p2) {}
	// Ax + By + C = 0 を満たす直線を生成
	Segment(double A, double B, double C) {
		if (std::abs(A) < EPS && std::abs(B) < EPS) {
			abort();
		} else if (std::abs(A) < EPS) {
			*this = Segment(Point(0, -C / B), Point(1, -C / B));
		} else if (std::abs(B) < EPS) {
			*this = Segment(Point(-C / A, 0), Point(-C / A, 1));
		} else {
			*this = Segment(Point(0, -C / B), Point(-C / A, 0));
		}
	}
	bool operator < (const Segment &s) const {
		return p1!=s.p1 ? p1<s.p1 : p2<s.p2;
	}
	bool operator > (const Segment &s) const {
		return p1!=s.p1 ? p1>s.p1 : p2>s.p2;
	}
	bool operator == (const Segment &s) const {
		return p1==s.p1 && p2==s.p2;
	}
	bool operator != (const Segment &s) const {
		return !(*this==s);
	}
};
using Line = Segment;
std::ostream& operator<<(std::ostream& s, const Segment& se) {
	return s << "(" << se.p1 << ", " << se.p2 << ")";
}

//点を回転させる
//角度radはラジアンで指定すること
Vector rotate(Vector a, double rad){
	return Vector(a.x*cos(rad)-a.y*sin(rad), a.x*sin(rad)+a.y*cos(rad));
}
//90度左回転させたベクトルを返す
Vector rotate90(Vector a){
	return Vector(-a.y, a.x);
}
//180度回転させたベクトルを返す
Vector rotate180(Vector a){
	return Vector(-a.x, -a.y);
}
//ベクトルの内積
double dot(Vector a, Vector b){
	return a.x*b.x + a.y*b.y;
}
//ベクトルの外積
double cross(Vector a, Vector b){
	return a.x*b.y - a.y*b.x;
}
//ベクトルa,bの角度を[0, π]の範囲で返す
double angle(Vector a,Vector b){
	return acos(dot(a,b)/a.abs()/b.abs());
}
//直交判定
bool isOrthogonal(Vector a,Vector b){
	return equals(dot(a,b), 0.0);
}
bool isOrthogonal(Point a1,Point a2,Point b1,Point b2){
	return isOrthogonal(a1-a2, b1-b2);
}
bool isOrthogonal(Segment s1,Segment s2){
	return equals(dot(s1.p2-s1.p1, s2.p2-s2.p1), 0.0);
}
//平行判定
bool isParallel(Vector a,Vector b){
	return equals(cross(a,b), 0.0);
}
bool isParallel(Point a1,Point a2,Point b1,Point b2){
	return isParallel(a1-a2, b1-b2);
}
bool isParallel(Segment s1,Segment s2){
	return equals(cross(s1.p2-s1.p1, s2.p2-s2.p1), 0.0);
}
//射影
Point project(Segment s,Point p){
	Vector base = s.p2-s.p1;
	double r = dot(p-s.p1, base)/base.norm();
	return base*r + s.p1;
}
//反射
Point reflect(Segment s,Point p){
	return p + (project(s,p)-p)*2;
}

//3点の位置関係
//p0,p1,p2が反時計回りになる
static constexpr int COUNTER_CLOCKWISE = 1;
//p0,p1,p2が時計回りになる
static constexpr int CLOCKWISE = -1;
//p2,p0,p1がこの順で同一直線上にある
static constexpr int ONLINE_BACK = 2;
//p0,p1,p2がこの順で同一直線上にある
static constexpr int ONLINE_FRONT = -2;
//p2が線分p0p1上にある
static constexpr int ON_SEGMENT = 0;
/*
					COUNTER_CLOCKWISE

 ONLINE_BACK -- [p0 -- ON_SEGMENT -- p1] --- ONLINE_FRONT

						CLOCKWISE
*/
int ccw(Point p0, Point p1, Point p2){
	Vector a=p1-p0;
	Vector b=p2-p0;
	if(cross(a,b)>EPS)return COUNTER_CLOCKWISE;
	if(cross(a,b)<-EPS)return CLOCKWISE;
	if(dot(a,b)<-EPS)return ONLINE_BACK;
	if(a.norm()<b.norm())return ONLINE_FRONT;
	return ON_SEGMENT;
}

//線分p1p2と線分p3p4の交差判定
//端点が他方の線分上にある場合、線分二つが平行に重なる場合も交差しているとみなす
bool intersect(Point p1, Point p2, Point p3, Point p4){
	return (ccw(p1,p2,p3)*ccw(p1,p2,p4)<=0 && ccw(p3,p4,p1)*ccw(p3,p4,p2)<=0);
}
bool intersect(Segment s1, Segment s2){
	return intersect(s1.p1, s1.p2, s2.p1, s2.p2);
}

//二点間の距離
double getDistance(Point a,Point b){
	return (a-b).abs();
}
//点と直線の距離
double getDistanceLP(Line l,Point p){
	return std::abs(cross(l.p2-l.p1, p-l.p1)) / (l.p2-l.p1).abs();
}
//点と線分の距離
double getDistanceSP(Segment s,Point p){
	if(dot(s.p2-s.p1, p-s.p1)<0.)return (p-s.p1).abs();
	if(dot(s.p1-s.p2, p-s.p2)<0.)return (p-s.p2).abs();
	return getDistanceLP(s,p);
}
//線分と線分の距離
double getDistanceSS(Segment s1,Segment s2){
	if(intersect(s1,s2))return 0.;
	return min({getDistanceSP(s1,s2.p1), getDistanceSP(s1,s2.p2), getDistanceSP(s2,s1.p1), getDistanceSP(s2,s1.p2)});
}

//線分s1と線分s2の交点
Point getCrossPoint(Segment s1, Segment s2){
	double A = cross(s1.p2 - s1.p1, s2.p2 - s2.p1);
	double B = cross(s1.p2 - s1.p1, s1.p2 - s2.p1);
	if (std::abs(A) < EPS && std::abs(B) < EPS) return s1.p1;// same line
	if (std::abs(A) < EPS) assert(false);// !!!PRECONDITION NOT SATISFIED!!!
	return s2.p1 + (s2.p2 - s2.p1) * B / A;
}

//円
class Circle {
public:
	Point c;
	double r;
	//c:中心の点、r=半径
	Circle(Point c=Point(), double r=0.) : c(c), r(r) {}
	bool operator == (const Circle &circle) const {
		return c==circle.c && std::abs(r-circle.r)<EPS;
	}
};
std::ostream& operator<<(std::ostream& s, const Circle& c) {
	return s << "(c = " << c.c << ", r = " << c.r << ")";
}

//円cと直線lの交点を返す
vector<Point> getCrossPointCL(Circle &c, Line &l) {
	vector<Point> res;
	double d = getDistanceLP(l, c.c); // 中心と直線の距離
	if (std::abs(d - c.r) < EPS) { // 触れている
		res.push_back(project(l, c.c));
		return res;
	}
	if (d > c.r) return res; // 離れている
	Point h = project(l, c.c);
	Point u = (l.p2 - l.p1) * sqrt(c.r * c.r - d * d) / (l.p2 - l.p1).abs();
	res.push_back(h + u);
	res.push_back(h - u);
	return res;
}


//円c1,c2の交差判定
// 0 : 離れている
// 1 : c1 が c2 の中で内接
//-1 : c2 が c1 の中で内接
// 2 : 2つの交点を持つ
//-2 : 外接
// 3 : c1 が c2 の中
//-3 : c2 が c1 の中
int intersectCC(Circle &c1, Circle &c2) {
	double d = (c1.c - c2.c).abs();
	if (c1.r + c2.r < d) return 0;				   // 離れている
	if (std::abs(c1.r + c2.r - d) < EPS) return -2;  // 外接
	if (std::abs(d + c1.r - c2.r) < EPS) return +1;  // c1 が c2 の中で内接
	if (std::abs(d + c2.r - c1.r) < EPS) return -1;  // c2 が c1 の中で内接
	if (d + c1.r < c2.r) return +3;				  // c1 が c2 の中
	if (d + c2.r < c1.r) return -3;				  // c2 が c1 の中
	return 2;									// 2つの交点を持つ
}
//ベクトルpとx軸との角度を返す 返却値の範囲[-π, π]
inline double arg(Vector p){ return atan2(p.y, p.x); }
inline double arg(Line l){ return arg(Point(l.p1.x-l.p2.x, l.p1.y-l.p2.y)); }
//大きさa, x軸との角度radのベクトルを返す
inline Vector polar(double a, double rad){ return Point(cos(rad)*a, sin(rad)*a); }
//円c1,c2の交点を返す
vector<Point> getCrossPointCC(Circle &c1, Circle &c2) {
	vector<Point> res;
	if (c1.c == c2.c) return res; // 中心が同じ
	int i = intersectCC(c1, c2);
	if (i == +1 || i == -1) { // 内接
		double d = (c1.c - c2.c).abs();
		if (c2.r < c1.r)
			res.push_back(c1.c + (c2.c - c1.c) * c1.r / d);
		else
			res.push_back(c2.c + (c1.c - c2.c) * c2.r / d);
		return res;
	}
	if (i == -2) { // 外接
		res.push_back((c1.c * c2.r + c2.c * c1.r) / (c1.r + c2.r));
		return res;
	}
	if (i == 0 || i == +3 || i == -3) { // 共通部分なし || 内部
		return res;
	}
	// 2つの交点を持つ
	double d = (c1.c-c2.c).abs();
	double a = acos((c1.r*c1.r+d*d-c2.r*c2.r)/(c1.r*d*2.));
	double t = arg(c2.c-c1.c);
	res.push_back(c1.c+polar(c1.r,t+a));
	res.push_back(c1.c+polar(c1.r,t-a));
	return res;
}
//点pを通る円cの接線について、円cで接する接点を返す
vector<Point> tangentPoints(Circle c, Point p){
	//複素数表示α=a+ib, β=c+id の積mul αβ=(a+ib)(c+id)=(ac–bd)+i(ad+bc)
	auto mul = [](Point a, Point b){
		return Point(a.x*b.x-a.y*b.y, a.x*b.y+a.y*b.x);
	};
	vector<Point> res;
	Point a = c.c;
	double ar = c.r;
	double sin = ar / (p-a).abs();
	if(sin > 1.+EPS) return res;
	double t = M_PI_2 - asin(min(sin, 1.));
	res.push_back(a + mul((p-a), polar(sin, t)));
	if(!equals(sin, 1.)) res.push_back(a + mul((p-a), polar(sin, -t)));
	return res;
}

//円c1,c2の共通接線を返す
//line.p1はc1での接点, line.p2はc2上での接点
vector<Line> tangentLines(Circle c1, Circle c2){
	//複素数表示α=a+ib, β=c+id の積mul αβ=(a+ib)(c+id)=(ac–bd)+i(ad+bc)
	auto mul = [](Point a, Point b){
		return Point(a.x*b.x-a.y*b.y, a.x*b.y+a.y*b.x);
	};
	Point a = c1.c, b = c2.c;
	double ar = c1.r, br = c2.r;
	vector<Line> ls;
	double d = (b-a).abs();

	for(ll i=0; i<2; i++){
		double sin = (ar - (1-i*2)*br) / d;
		if(sin*sin > 1.+EPS) break;

		double cos = sqrt(max(1 - sin*sin, 0.0));
		for(ll j=0; j<2; j++) {
			Point n = mul((b-a), Point(sin, (1-j*2)*cos) / d);
			ls.push_back(Line(a + n*ar, b + n*(1-i+2)*br));
			if(cos < EPS) break;
		}
	}
	return ls;
}



//using Polygon = vector<Point>;
//多角形gと点pの内包関係を返す
static constexpr int INSIDE = 2;
static constexpr int ONLINE = 1;
static constexpr int OUTSIDE = 0;
ll contains(vector<Point> &g, Point p){
	ll n=g.size();
	bool x=false;
	for(ll i=0; i<n; i++){
		Point a=g[i]-p, b=g[(i+1)%n]-p;
		if(std::abs(cross(a,b)) < EPS && dot(a,b) < EPS) return ONLINE;
		if(a.y > b.y) swap(a,b);
		if(a.y < EPS && EPS < b.y && cross(a,b) > EPS) x=!x;
	}
	return (x ? INSIDE : OUTSIDE);
}

//点の集合sに対する凸包を返す 
vector<Point> andrewScan(vector<Point> &s){
	vector<Point> u,l;
	if(s.size()<3) return s;
	sort(s.begin(), s.end());
	u.push_back(s[0]);
	u.push_back(s[1]);
	l.push_back(s[s.size()-1]);
	l.push_back(s[s.size()-2]);

	for(ll i=2; i<(ll)s.size(); i++){
		for(ll n=u.size(); n>=2 && ccw(u[n-2],u[n-1],s[i])==COUNTER_CLOCKWISE; n--){
			u.pop_back();
		}
		u.push_back(s[i]);
	}
	for(ll i=s.size()-3; i>=0; i--){
		for(ll n=l.size(); n>=2 && ccw(l[n-2],l[n-1],s[i])==COUNTER_CLOCKWISE; n--){
			l.pop_back();
		}
		l.push_back(s[i]);
	}

	reverse(l.begin(), l.end());
	for(ll i=u.size()-2; i>=1; i--)l.push_back(u[i]);
	return l;
}

//線分の集合sの交点の数を返す
class EndPoint {
public:
	Point p;
	ll seg,st; //入力線分のID, 端点の種類
	EndPoint() {}
	EndPoint(Point p, ll seg, ll st) : p(p), seg(seg), st(st) {}

	bool operator < (const EndPoint &ep) const {
		if(p.y == ep.p.y) return st < ep.st;
		return p.y < ep.p.y;
	}
};
vector<Point> manhattanIntersection(vector<Segment> &S){
	static const int BOTTOM = 0;
	static const int LEFT = 1;
	static const int RIGHT = 2;
	static const int TOP = 3;
	ll n=S.size();
	vector<EndPoint> EP(2*n);
	for(ll i=0,k=0; i<n; i++){
		if(S[i].p1.y==S[i].p2.y){
			if(S[i].p1.x>S[i].p2.x) swap(S[i].p1, S[i].p2);
		}else if(S[i].p1.y > S[i].p2.y){
			swap(S[i].p1, S[i].p2);
		}

		if(S[i].p1.y==S[i].p2.y){
			EP[k++]=EndPoint(S[i].p1, i, LEFT);
			EP[k++]=EndPoint(S[i].p2, i, RIGHT);
		}else{
			EP[k++]=EndPoint(S[i].p1, i, BOTTOM);
			EP[k++]=EndPoint(S[i].p2, i, TOP);
		}
	}

	sort(EP.begin(), EP.end());

	set<ll> BT;
	BT.insert(INF);
	vector<Point> ans;
	for(ll i=0; i<2*n; i++){
		if(EP[i].st==TOP){
			BT.erase(EP[i].p.x);
		}else if(EP[i].st==BOTTOM){
			BT.insert(EP[i].p.x);
		}else if(EP[i].st==LEFT){
			auto b=BT.lower_bound(S[EP[i].seg].p1.x);
			auto e=BT.upper_bound(S[EP[i].seg].p2.x);
			for(; b!=e; advance(b,1)){
				ans.push_back(Point(*b,EP[i].p.y));
			}
			
		}
	}
	return ans;
}

//最小包含円(pointvの点を内部に含む半径最小の円)を返す
//ハックのあるコンテストではseedに time(0), random_device()() を渡した方がよい
Circle minimumBoundingCircle(vector<Point> &pointv, ll seed = 2326) {
	const ll n = pointv.size();
	assert(n >= 1);
	if (n == 1) {
		return Circle(pointv[0], 0.);
	}

	std::mt19937 mt(seed);
	std::shuffle(pointv.begin(), pointv.end(), mt);
	// std::random_shuffle(left, right); // simple but deprecated

	auto make_circle_3 = [](Point &a, Point &b, Point &c) -> Circle {
		double A = (b - c).norm();
		double B = (c - a).norm();
		double C = (a - b).norm();
		double S = cross(b - a, c - a);
		Point p = (a * A * (B + C - A) + b * B * (C + A - B)  + c * C * (A + B - C)) / (S * S * 4.);
		double r2 = (p - a).abs();
		return Circle(p, r2);
	};

	auto make_circle_2 = [](Point &a, Point &b) -> Circle {
		Point c = (a + b) / 2.;
		double r2 = (a - c).abs();
		return Circle(c, r2);
	};

	auto in_circle = [](Circle &c, Point &a) -> bool {
		return (a - c.c).norm() <= c.r * c.r + EPS;
	};

	Circle c = make_circle_2(pointv[0], pointv[1]);

	// MiniDisc
	for (ll i = 2; i < n; ++i) {
		if (!in_circle(c, pointv[i])) {
			// MiniDiscWithPoint
			c = make_circle_2(pointv[0], pointv[i]);
			for (ll j = 1; j < i; ++j) {
				if (!in_circle(c, pointv[j])) {
					// MiniDiscWith2Points
					c = make_circle_2(pointv[i], pointv[j]);
					for (ll k = 0; k < j; ++k) {
						if (!in_circle(c, pointv[k])) {
							c = make_circle_3(pointv[i], pointv[j], pointv[k]);
						}
					}
				}
			}
		}
	}
	return c;
}


//最近点対(距離が最小の2点)を返す
//関数適用後、pointsには破壊的操作(y座標によるソート)が行われる点に注意
pair<Point,Point> closest_pair(vector<Point> &points){
	auto closest_pair_core = [&](auto&& closest_pair_core, std::vector<Point>::iterator left, std::vector<Point>::iterator right) -> pair<double, pair<Point,Point>> {
		ll n = distance(left, right);
		if (n == 1) {
			return {numeric_limits<double>::max(), {*left, *left}};
		}
		if (n == 2) {
			if(left[0].y > left[1].y) swap(left[0], left[1]);
			return {(left[0]-left[1]).abs(), {left[0], left[1]}};
		}
		
		std::vector<Point>::iterator middle = next(left, n/2);
		double x = middle->x;
		pair<double, pair<Point,Point>> d1 = closest_pair_core(closest_pair_core, left, middle);
		pair<double, pair<Point,Point>> d2 = closest_pair_core(closest_pair_core, middle, right);
		pair<double, pair<Point,Point>> d = (d1.first < d2.first) ? d1 : d2;

		std::inplace_merge(left, middle, right,
			[](const Point &a, const Point &b) { return a.y < b.y; });

		vector<std::vector<Point>::iterator> around;
		for(auto i = left; i != right; ++i){
			if(std::abs(i->x - x) >= d.first) continue;
			for(auto j = around.rbegin(); j != around.rend(); ++j){
				double dx = i->x - (*j)->x;
				double dy = i->y - (*j)->y;
				if (dy >= d.first) break;
				double absval = sqrt(dx * dx + dy * dy);
				if (d.first > absval) {
					d = {absval, {*i, **j}};
				}
			}
			around.push_back(i);
		}
		return d;
	};
	sort(points.begin(), points.end());
	return closest_pair_core(closest_pair_core, points.begin(), points.end()).second;
}

//pointsで囲まれた領域の面積を返す
double area2(vector<Point>& points) {
	double s = 0;
	ll n = points.size();
	for (int i = 0; i < n; ++i) s += cross(points[i], points[(i + 1) % n]);
	return s / 2.;
}

//キャリパー法により、pointsの中で最も遠い2点(最遠点対)を返す
//pointsが凸多角形であることが分かっている場合、andrewScan省略してもいいです
pair<Point,Point> convex_diameter(vector<Point> &points) {
	vector<Point> ps=andrewScan(points);
	ll n = ps.size();
	ll i = min_element(ps.begin(), ps.end()) - ps.begin();
	ll j = max_element(ps.begin(), ps.end()) - ps.begin();
	ll maxI, maxJ;
	double maxD = 0;
	for(ll k=0; k<2*n; k++) {
		if(maxD < (ps[i] - ps[j]).norm()) {
			maxD = (ps[i] - ps[j]).norm();
			maxI = i;
			maxJ = j;
		}
		if(cross(ps[i] - ps[(i+1) % n], ps[(j+1) % n] - ps[j]) <= 0) j = (j+1) % n;
		else i = (i+1) % n;
	}
	return {ps[maxI], ps[maxJ]};
}

//多角形pointsを直線lで切り，新しく出来た2つの多角形を求める
//直線lの進行方向に対して左側の多角形のみ返す
vector<Point> convex_cut(vector<Point> &points, Line &l) {
	vector<Point> res;
	ll n = points.size();
	for (ll i = 0; i < n; ++i) {
		Point A = points[i], B = points[(i + 1) % n];
		if (ccw(l.p1, l.p2, A) != CLOCKWISE) res.push_back(A);
		if (ccw(l.p1, l.p2, A) * ccw(l.p1, l.p2, B) < 0) res.push_back(getCrossPoint(Line(A, B), l));
	}
	return res;
}

/*-----8<-----library-----8<-----*/

constexpr ll N_MAX = 60;
constexpr ll X_I_MAX = 1000;
constexpr ll Y_I_MAX = 1000;
constexpr ll C_I_MAX = 100;

ll N, K;
vector<ll> x;
vector<ll> y;
vector<ll> c;

void solve() {
	scanf("%lld%lld", &N, &K);
	x.assign(N, 0);
	y.assign(N, 0);
	c.assign(N, 0);
	rep(i, N) { scanf("%lld%lld%lld", &x[i], &y[i], &c[i]); }
	
	vector<Point> vraw;
	rep(i,N){
		vraw.emplace_back(x[i],y[i]);
	}


	//初期は left->OK / right->NG になっています
	double left = INF;
	double right = 0;
	auto isOK = [&](double val) -> bool {
		vector<Point> v=vraw;
		rep(i,N)for(ll j=i+1;j<N;j++){
			Circle c1(Point(x[i],y[i]), val/c[i]);
			Circle c2(Point(x[j],y[j]), val/c[j]);
			vector<Point> t=getCrossPointCC(c1,c2);
			rep(k,t.size())v.push_back(t[k]);
		}
		debug(val);
		debug(v);
		rep(j,v.size()){
			ll count=0;
			rep(i,N){
				double d=getDistance(v[j],Point(x[i],y[i]));
				if(d*c[i]<val+EPS)count++;
			}
			debug(count);
			if(count>=K)return true;
		}
		
		return false;		
	};
	while(abs(right - left) > 1e-7) {
		double mid = left + (right - left) / 2;
		if(isOK(mid)) left = mid;
		else right = mid;
	}
	cout.setf(ios::fixed), cout.precision(20);
	p(left);	
}

// https://atcoder.jp/contests/abc157/tasks/abc157_f
signed main() {
	solve();
	return 0;
}


Measured memory_bytes: 384