#include <bits/stdc++.h>
using namespace std;
#ifdef 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 << std::endl; }
	template<typename Head, typename... Tail> void debug_impl(Head head, Tail... tail) { std::cerr << " " << head << (sizeof...(tail) ? "," : ""); debug_impl(tail...); }
	#define debug(...) { std::cerr << std::boolalpha << "(" << #__VA_ARGS__ << ") ="; debug_impl(__VA_ARGS__); std::cerr << std::noboolalpha; }
#else
	#define debug(...) {}
#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>
	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 typename std::vector<T>::iterator first, const typename std::vector<T>::iterator last) : std::vector<T>(first, last) {}
		dvector(const std::string::iterator first, const std::string::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() << std::endl; 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() << std::endl; 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 dvector<T>& v) {
		for (int i = 0, len = v.size(); i < len; ++i){ s << v[i]; if (i < len - 1) s << "\t"; } return s; }
	template<typename T> std::ostream& operator<<(std::ostream& s, const dvector< dvector<T> >& vv) {
		for (int i = 0, len = vv.size(); i < len; ++i){ s << vv[i] << std::endl; } 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 T1, typename T2> std::ostream& operator<<(std::ostream& s, const std::map<T1, T2>& m) {
		s << "{" << std::endl; for (auto itr = m.begin(); itr != m.end(); ++itr){ s << "\t" << (*itr).first << " : " << (*itr).second << std::endl; } 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() << std::endl; throw SIGFPE_exception();	}
	void catch_SIGSEGV(int e) { std::cerr << boost::stacktrace::stacktrace() << std::endl; 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(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(vector<T> &v) { v.erase(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 x!=p.x ? 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;
	}
	
};
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 &p) const {
		return p1==p.p1 && p2==p.p2;
	}
};
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;
}

//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 getDistance(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;
}
//円の交差判定
// 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つの交点を持つ
}
//円c1,c2の交点を返す
vector<Point> getCrossPointCC(Circle &c1, Circle &c2) {
	vector<Point> res;
	double r1 = c1.r, r2 = c2.r, d = (c1.c - c2.c).abs();
	if (c1.c == c2.c) return res; // 中心が同じ
	int i = intersectCC(c1, c2);
	if (i == +1 || i == -1) { // 内接
		if (r2 < r1)
			res.push_back(c1.c + (c2.c - c1.c) * r1 / d);
		else
			res.push_back(c2.c + (c1.c - c2.c) * r2 / d);
		return res;
	}
	if (i == -2) { // 外接
		res.push_back((c1.c * c1.r + c2.c * c2.r) / (c1.r + c2.r));
		return res;
	}
	if (i == 0 || i == +3 || i == -3) { // 共通部分なし || 内部
		return res;
	}
	// 2つの交点を持つ
	Point p = c1.c - c2.c;
	double A = -2. * p.x, B = 2 * p.y;
	double C = (c1.c).abs() - (c2.c).abs() - r1 * r1 + r2 * r2;
	Line l(A, B, C);
	return getCrossPointCL(c1, l);  // Ax + By + C = 0
}


//ベクトル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軸との角度rのベクトルを返す
inline Vector polar(double a, double r){ return Point(cos(r)*a, sin(r)*a); }
//円c1と円c2の交点を返す
pair<Point,Point> getCrossPoints(Circle c1, Circle c2){
	assert(getDistance(c1.c,c2.c) < c1.r+c2.r+EPS);
	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);
	return {c1.c+polar(c1.r,t+a), c1.c+polar(c1.r,t-a)};
}

using Polygon = vector<Point>;
//多角形gと点pの内包関係を返す
static constexpr int INSIDE = 2;
static constexpr int ONLINE = 1;
static constexpr int OUTSIDE = 0;
ll contains(Polygon &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に対する凸包を返す 
Polygon andrewScan(Polygon &s){
	Polygon 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 = [](Point &a, Circle &c) -> 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(pointv[i], c)) {
			// MiniDiscWithPoint
			c = make_circle_2(pointv[0], pointv[i]);
			for (ll j = 1; j < i; ++j) {
				if (!in_circle(pointv[j], c)) {
					// MiniDiscWith2Points
					c = make_circle_2(pointv[i], pointv[j]);
					for (ll k = 0; k < j; ++k) {
						if (!in_circle(pointv[k], c)) {
							c = make_circle_3(pointv[i], pointv[j], pointv[k]);
						}
					}
				}
			}
		}
	}
	return c;
}


//最近点対(距離が最小の2点)を返す
//関数適用後、pointsには破壊的操作(y座標によるソート)が行われる点に注意
//使うときは closest_pair(points) を呼んでください
template<class iter>
pair<double, pair<Point,Point>> closest_pair_core(iter left, iter right) {
		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]}};
		}
        
		iter middle = next(left, n/2);
        double x = middle->x;
		pair<double, pair<Point,Point>> d1 = closest_pair_core(left, middle);
		pair<double, pair<Point,Point>> d2 = 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<iter> around;
		for(iter 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;
}
pair<Point,Point> closest_pair(vector<Point> &points){
	sort(points.begin(), points.end());
	return 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.;
}

//キャリパー法により、凸多角形の中から最も遠い2点を返す
pair<Point,Point> convex_diameter(vector<Point> &ps) {
	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<-----*/



//http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_2_A&lang=ja
void CGL_2_A(){
	ll N;
	cin>>N;
	vector<ll> ans(N,0);
	rep(i,N){
		double x0,y0,x1,y1,x2,y2,x3,y3;
		cin>>x0>>y0>>x1>>y1>>x2>>y2>>x3>>y3;
		Point p0(x0,y0),p1(x1,y1),p2(x2,y2),p3(x3,y3);
		ll t=0;
		if(isOrthogonal(p0,p1,p2,p3)){
			t=1;
		}else if(isParallel(p0,p1,p2,p3)){
			t=2;
		}
		ans[i]=t;
	}
	rep(i,N)p(ans[i]);
}

//http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_1_A&lang=ja
void CGL_1_A(){
	double x0,y0,x1,y1;
	cin>>x0>>y0>>x1>>y1;
	Line l(Point(x0,y0),Point(x1,y1));
	ll Q;
	cin>>Q;
	vector<Point> ans(Q,0);
	rep(i,Q){
		double xq,yq;
		cin>>xq>>yq;
		Point po(xq,yq);
		Point t=project(l,po);
		ans[i]=t;
	}
	cout.setf(ios::fixed), cout.precision(20);
	rep(i,Q){
		cout<<ans[i].x<<' '<<ans[i].y<<'\n';
	}
}

//http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_1_B&lang=ja
void CGL_1_B(){
	double x0,y0,x1,y1;
	cin>>x0>>y0>>x1>>y1;
	Line l(Point(x0,y0),Point(x1,y1));
	ll Q;
	cin>>Q;
	vector<Point> ans(Q,0);
	rep(i,Q){
		double xq,yq;
		cin>>xq>>yq;
		Point po(xq,yq);
		Point t=reflect(l,po);
		ans[i]=t;
	}
	cout.setf(ios::fixed), cout.precision(20);
	rep(i,Q){
		cout<<ans[i].x<<' '<<ans[i].y<<'\n';
	}
}

//http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_2_D&lang=ja
void CGL_2_D(){
	ll Q;
	cin>>Q;
	vector<double> ans(Q,0);
	rep(i,Q){
		double x0,y0,x1,y1,x2,y2,x3,y3;
		cin>>x0>>y0>>x1>>y1>>x2>>y2>>x3>>y3;
		Segment s0(Point(x0,y0),Point(x1,y1)), s1(Point(x2,y2),Point(x3,y3));
		double t=getDistance(s0,s1);
		ans[i]=t;
	}
	cout.setf(ios::fixed), cout.precision(20);
	rep(i,Q)p(ans[i]);
}

//http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_1_C&lang=ja
void CGL_1_C(){
	double x0,y0,x1,y1;
	cin>>x0>>y0>>x1>>y1;
	Point p0(x0,y0),p1(x1,y1);
	ll Q;
	cin>>Q;
	vector<string> ans(Q,"");
	map<ll,string> m;
	m[1]="COUNTER_CLOCKWISE";
	m[-1]="CLOCKWISE";
	m[2]="ONLINE_BACK";
	m[-2]="ONLINE_FRONT";
	m[0]="ON_SEGMENT";
	rep(i,Q){
		double xq,yq;
		cin>>xq>>yq;
		Point pq(xq,yq);
		ll t=ccw(p0,p1,pq);
		ans[i]=m[t];
	}
	rep(i,Q)p(ans[i]);
}

//http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_2_B&lang=ja
void CGL_2_B(){
	ll Q;
	cin>>Q;
	vector<ll> ans(Q,0);
	rep(i,Q){
		double x0,y0,x1,y1,x2,y2,x3,y3;
		cin>>x0>>y0>>x1>>y1>>x2>>y2>>x3>>y3;
		Point p0(x0,y0),p1(x1,y1),p2(x2,y2),p3(x3,y3);
		bool t=intersect(p0,p1,p2,p3);
		ans[i]=t ? 1 : 0;
	}
	rep(i,Q)p(ans[i]);	
}

//http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_2_C&lang=ja
void CGL_2_C(){
	ll Q;
	cin>>Q;
	vector<Point> ans(Q,0);
	rep(i,Q){
		double x0,y0,x1,y1,x2,y2,x3,y3;
		cin>>x0>>y0>>x1>>y1>>x2>>y2>>x3>>y3;
		Point p0(x0,y0),p1(x1,y1),p2(x2,y2),p3(x3,y3);
		Segment s0(p0,p1),s1(p2,p3);
		Point t=getCrossPoint(s0,s1);
		ans[i]=t;
	}
	cout.setf(ios::fixed), cout.precision(20);
	rep(i,Q)p(ans[i].x,ans[i].y);
}

//http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_7_D&lang=ja
void CGL_7_D(){
	ll cx,cy,r,Q;
	cin>>cx>>cy>>r>>Q;
	Circle c(Point(cx,cy),r);
	vector<pair<Point,Point>> ans(Q);
	rep(i,Q){
		double x0,y0,x1,y1;
		cin>>x0>>y0>>x1>>y1;
		Point p0(x0,y0),p1(x1,y1);
		Line l(p0,p1);
		vector<Point> tv=getCrossPointCL(c,l);
		pair<Point,Point> t;
		if(tv.size()==2)t={tv[0],tv[1]};
		else t={tv[0],tv[0]};
		if(t.first.x>t.second.x || (equals(t.first.x,t.second.x) && t.first.y>t.second.y))swap(t.first,t.second);
		ans[i]=t;
	}
	cout.setf(ios::fixed), cout.precision(20);
	rep(i,Q)p(ans[i].first.x, ans[i].first.y, ans[i].second.x, ans[i].second.y);
}

//http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_7_E&lang=ja
void CGL_7_E(){
	double c0x,c0y,r0,c1x,c1y,r1;
	cin>>c0x>>c0y>>r0>>c1x>>c1y>>r1;
	Circle c0(Point(c0x,c0y), r0), c1(Point(c1x,c1y), r1);
	pair<Point,Point> t=getCrossPoints(c0, c1);
	if(t.first.x>t.second.x || (equals(t.first.x,t.second.x) && t.first.y>t.second.y))swap(t.first,t.second);
	cout.setf(ios::fixed), cout.precision(20);
	p(t.first.x, t.first.y, t.second.x, t.second.y);
}

//http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_3_C&lang=ja
void CGL_3_C(){
	ll N;
	cin>>N;
	vector<Point> g(N);
	rep(i,N)cin>>g[i].x>>g[i].y;
	ll Q;
	cin>>Q;
	vector<ll> ans(Q,0);
	rep(i,Q){
		ll x,y;
		cin>>x>>y;
		ll t=contains(g,Point(x,y));
		ans[i]=t;
	}
	rep(i,Q)p(ans[i]);
}

//http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_4_A&lang=ja
void CGL_4_A(){
	ll N;
	cin>>N;
	vector<Point> g(N);
	rep(i,N)cin>>g[i].x>>g[i].y;
	vector<Point> ch=andrewScan(g);
	printf("%lld\n",(ll)ch.size());
	ll f=0;
	repeq(i,ch.size()-1){
		if(ch[f].y>ch[i].y || (ch[f].y==ch[i].y && ch[f].x>ch[i].x)){
			f=i;
		}
	}
	rep(i,ch.size()){
		printf("%lld %lld\n",(ll)ch[(i+f)%ch.size()].x, (ll)ch[(i+f)%ch.size()].y);
	}
}

//http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_6_A&lang=ja
void CGL_6_A(){
	ll N;
	cin>>N;
	vector<Segment> a(N);
	rep(i,N)cin>>a[i].p1.x>>a[i].p1.y>>a[i].p2.x>>a[i].p2.y;
	vector<Point> ans=manhattanIntersection(a);
	p(ans.size());
}

//https://atcoder.jp/contests/abc151/tasks/abc151_f
void ABC151F() {
	ll N;
	cin>>N;
	vector<double> x(N,0),y(N,0);
	rep(i, N) { cin>>x[i]>>y[i]; }
	vector<Point> v;
	rep(i,N){
		v.emplace_back(x[i],y[i]);
	}
	Circle ans=minimumBoundingCircle(v);
	cout.setf(ios::fixed), cout.precision(20);
	p(ans.r);
}

//http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_5_A&lang=ja
void CGL_5_A() {
	ll N;
	cin>>N;
	vector<double> x(N,0),y(N,0);
	rep(i, N) { cin>>x[i]>>y[i]; }
	vector<Point> v;
	rep(i,N){
		v.emplace_back(x[i],y[i]);
	}
	pair<Point,Point> anspr=closest_pair(v);
	double ans=getDistance(anspr.first, anspr.second);
	cout.setf(ios::fixed), cout.precision(20);
	p(ans);
}

//http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_3_A&lang=ja
void CGL_3_A(){
	ll N;
	cin>>N;
	vector<double> x(N,0),y(N,0);
	rep(i, N) { cin>>x[i]>>y[i]; }
	vector<Point> v;
	rep(i,N){
		v.emplace_back(x[i],y[i]);
	}
	double ans=area2(v);
	cout.setf(ios::fixed), cout.precision(1);
	p(ans);
}

//http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_3_B&lang=ja
void CGL_3_B(){
	ll N;
	cin>>N;
	vector<double> x(N,0),y(N,0);
	rep(i, N) { cin>>x[i]>>y[i]; }
	vector<Point> v;
	rep(i,N){
		v.emplace_back(x[i],y[i]);
	}
	if(N==3){
		ll cc=ccw(v[0],v[1],v[2]);
		if(cc!=CLOCKWISE && cc!=COUNTER_CLOCKWISE){
			p(1);return;
		}
	}
	vector<Point> convex=andrewScan(v);
	if(v.size()==convex.size())p(1);
	else p(0);
}

//http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_4_B&lang=ja
void CGL_4_B(){
	ll N;
	cin>>N;
	vector<double> x(N,0),y(N,0);
	rep(i, N) { cin>>x[i]>>y[i]; }
	vector<Point> v;
	rep(i,N){
		v.emplace_back(x[i],y[i]);
	}
	pair<Point,Point> anspr=convex_diameter(v);
	cout.setf(ios::fixed), cout.precision(20);
	p(getDistance(anspr.first, anspr.second));
}

//http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_4_C&lang=ja
void CGL_4_C(){
	ll N;
	cin>>N;
	vector<double> x(N,0),y(N,0);
	rep(i, N) { cin>>x[i]>>y[i]; }
	vector<Point> v;
	rep(i,N){
		v.emplace_back(x[i],y[i]);
	}
	ll Q;
	cin>>Q;
	vector<double> ans(Q,0);
	rep(i,Q){
		ll s1,s2,t1,t2;
		cin>>s1>>s2>>t1>>t2;
		Line l(Point(s1,s2),Point(t1,t2));
		vector<Point> cutv=convex_cut(v,l);
		double a=area2(cutv);
		debug(cutv,a);
		ans[i]=a;
	}
	cout.setf(ios::fixed), cout.precision(20);
	rep(i,Q)p(ans[i]);
}

//http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_7_A&lang=ja
void CGL_7_A(){
	map<ll,ll> m;
	m[0]=4;
	m[1]=1;
	m[-1]=1;
	m[2]=2;
	m[-2]=3;
	m[3]=0;
	m[-3]=0;
	ll c1x,c1y,c1r,c2x,c2y,c2r;
	cin>>c1x>>c1y>>c1r>>c2x>>c2y>>c2r;
	Circle c1(Point(c1x,c1y),c1r), c2(Point(c2x,c2y),c2r);
	p(m[intersectCC(c1,c2)]);
}

signed main() {
	//CGL_2_A();
	//CGL_1_A();
	//CGL_1_B();
	//CGL_2_D();
	//CGL_1_C();
	//CGL_2_B();
	//CGL_2_C();
	CGL_7_D();
	//CGL_7_E();
	//CGL_3_C();
	//CGL_4_A();
	//CGL_6_A();
	//ABC151F();
	//CGL_5_A();
	//CGL_3_A();
	//CGL_3_B();
	//CGL_4_B();
	//CGL_4_C();
	//CGL_7_A();


	return 0;
}



Measured memory_bytes: 3344