Problem: For given a circle $c$ and a line $l$, print the coordinates of the cross points of them.

Constraints

* $p1$ and $p2$ are different
* The circle and line have at least one cross point
* $1 \leq q \leq 1,000$
* $-10,000 \leq cx, cy, x1, y1, x2, y2 \leq 10,000$
* $1 \leq r \leq 10,000$

Input

The input is given in the following format.

$cx\; cy\; r$
$q$
$Line_1$
$Line_2$
:
$Line_q$


In the first line, the center coordinate of the circle and its radius are given by $cx$, $cy$ and $r$. In the second line, the number of queries $q$ is given.

In the following $q$ lines, as queries, $Line_i$ are given ($1 \leq i \leq q$) in the following format.

$x_1\; y_1\; x_2\; y_2$

Each line is represented by two points $p1$ and $p2$ which the line crosses. The coordinate of $p1$ and $p2$ are given by ($x1$, $y1$) and ($x2$, $y2$) respectively. All input values are given in integers.

Output

For each query, print the coordinates of the cross points in the following rules.

* If there is one cross point, print two coordinates with the same values.
* Print the coordinate with smaller $x$ first. In case of a tie, print the coordinate with smaller $y$ first.



The output values should be in a decimal fraction with an error less than 0.000001.

Example

Input

2 1 1
2
0 1 4 1
3 0 3 3


Output

1.00000000 1.00000000 3.00000000 1.00000000
3.00000000 1.00000000 3.00000000 1.00000000

Solution (in CPP):

Solution:
#include<bits/stdc++.h>
/*
#include<array>
#include<vector>
#include<iostream>
#include<cmath>
*/

using namespace std;

typedef double Real;
constexpr Real EPS = 1e-8;

enum { CCW=1, CW = -1, BACK= 2, FRONT=-2, ON=0}; //Counter Clock Wise

//???????????£
int sign(Real d) {
	if (d>EPS) { return 1; }
	if (d<-EPS) { return -1; }
	return 0;
}

/*
 * ???????§?????????????
 */
struct Point {
	Real x,y;

	//Point p(2,3)????¨±???
	explicit Point(Real x_=0, Real y_=0): x(x_), y(y_) {} //explicit?????£??\Point p = x;????¨±????????????????????????

	Point operator+(const Point &p) const {
		return Point(x+p.x,y+p.y);
	}
	Point operator-(const Point &p) const {
		return Point(x-p.x,y-p.y);
	}
	Point operator*(Real s) const {
		return Point(x*s,y*s);
	}
	Point operator/(Real s) const {
		return Point(x/s,y/s);
	}
	bool operator<(const Point &p) const {
		return sign(x - p.x) == -1 || (sign(x - p.x)==0 && sign(y - p.y)==-1);
	}
	bool operator==(const Point &p) const { return sign(x-p.x) == 0 && sign(y - p.y)==0; }

};

//Point??????????????°????????¬??????
istream &operator>>(istream &is, Point &p) {
	return is >> p.x >> p.y;
}
ostream &operator<<(ostream &os, const Point &p) {
	//return os << '(' << p.x << ", " << p.y << ')';
	return os << p.x << " " << p.y;
}

struct Line : public array<Point, 2> { //??????
	Line(const Point &a, const Point &b) { at(0) = a; at(1) = b; }
};

struct Segment : public array<Point, 2> { //??´???
	Segment(const Point &a, const Point &b) { at(0) = a; at(1) = b; }
};

/*
 *???
 */
struct Circle {
	Point c;
	Real r;
	Circle(const Point &c_, Real r_): c(c_), r(r_) {}
};

/*
 * ????§???¢
 */
typedef vector<Point> Polygon;



/*
 * Calc
 */
//???????¨??????????90??????
Point rotate90(const Point &p) { return Point(-p.y,p.x); }

//???????¨???????????????±???
Point rotate(const Point &p, Real theta) {
	const Real s = sin(theta), c = cos(theta);
	return Point(c*p.x - s*p.y, s*p.x + c*p.y);
}

//[X???]??¨[???????????????P??????]????§????
Real angle(const Point &p) { return atan2(p.y, p.x); }

//??????0????????????P?????§????????¢?????????
Real norm(const Point &p) { return p.x * p.x + p.y * p.y; }

//??????0????????????P?????§????????¢
Real abs(const Point &p) { return sqrt(norm(p)); }

//????????????
Real dot(const Point &a, const Point &b) { return a.x * b.x + a.y * b.y; } //??????(?????????????????£?????????)
Real cross(const Point &a, const Point &b) { return a.x * b.y - a.y * b.x; } //??????

 //?°???±
Point project(const Line &l, const Point &p) {
	const Point a = p - l[0];
	const Point b = l[1] - l[0];
	return l[0] + b * (dot(a,b) / norm(b));
}
//???????§°
Point reflect(const Line &l, const Point &p) {
	const Point t = project(l, p);
	return t + (t-p);
}

//Counter Clock Wise
int ccw(const Point &a, const Point &b, const Point &c) { //????¨????????????¶??????
	const Point p = b - a;
	const Point q = c - a;
	const Real cr = cross(p,q);

	if (sign(cr) == 1) { return CCW; }
	if (sign(cr) == -1) { return CW; }
	if (sign(dot(p,q)) == -1) { return BACK; }
	if (sign(norm(p) - norm(q)) == -1) { return FRONT; }
	return ON;
}

//????????????
bool intersect(const Segment &s, const Point &p) {
	return ccw(s[0], s[1], p) == ON;
}

bool intersect(const Segment &a, const Segment &b) { //????????£?????????????????????
	return ccw(a[0], a[1], b[0]) * ccw(a[0], a[1], b[1]) <= 0 
		   && ccw(b[0], b[1], a[0]) * ccw(b[0], b[1], a[1]) <=0;
}

bool intersect(const Line &l, const Point &p) { //
	return abs(ccw(l[0], l[1], p)) != 1;
}

bool intersect(const Line &l, const Segment &s) { //
	return sign(cross(l[1] - l[0], s[0] - l[0]) * cross(l[1] - l[0], s[1] - l[0])) <=0;
}

bool intersect(const Line &a, const Line &b) { 
	return sign(cross(a[1]-a[0], b[1]-b[0])) != 0
		|| sign(cross(a[1]-a[0], b[1]-a[0])) == 0;
}


//?????¢
Real dist(const Point &a, const Point &b) {
	return abs(a - b);
}
Real dist(const Line &l, const Point &p) {
	Point a = l[1] - l[0];
	Point b = p - l[0];
	return abs(cross(a,b))/abs(a);
}
Real dist(const Line &l, const Segment &s) {
	if (intersect(l,s)) { return 0; }
	return min(dist(l,s[0]), dist(l,s[1]));
}
Real dist(const Line &a, const Line &b) {
	if (intersect(a,b)) { return 0; }
	return dist(a,b[0]);
}
Real dist(const Segment &s, const Point &p) {
	if (sign(dot(s[1] - s[0], p - s[0])) == -1) { return dist(s[0],p); } 
	if (sign(dot(s[0] - s[1], p - s[1])) == -1) { return dist(s[1],p); } 
	return dist(Line(s[0],s[1]), p);
}

Real dist(const Segment &a, const Segment &b) {
	if (intersect(a,b)) { return 0; }
	return min({dist(a,b[0]), dist(a,b[1]), dist(b,a[0]), dist(b,a[1])});
}

//???????????¨?????´?????¨????????????
bool intersect(const Circle &a, const Circle &b) {
	return sign(dist(a.c,b.c) - (a.r + b.r)) <= 0
		&& sign(dist(a.c,b.c) - abs(a.r - b.r)) >= 0;
}

bool intersect(const Circle &c, Segment &s) {
	return sign(dist(s, c.c) - c.r) <= 0;
}

bool intersect(const Circle &c, Line &l) {
	return sign(dist(l, c.c) - c.r) <= 0;
}


Point crosspoint(const Line &a, const Line &b) {
	assert(intersect(a,b));
	const Real crs = cross(a[1] - a[0], b[1] - b[0]);
	if (sign(crs) == 0) { return a[0]; };
	return b[0] + (b[1] - b[0]) * (cross(a[1]-a[0], a[1]-b[0]) / crs);
}

//??????
Point crosspoint(const Segment &a, const Segment &b) {
	assert(intersect(a,b));
	
	const Real crs = cross(a[1] - a[0], b[1] - b[0]);
	if (sign(crs) == 0) {
		if(intersect(a, b[0])) { return b[0]; }
		if(intersect(a, b[1])) { return b[1]; }
		if(intersect(b, a[0])) { return a[0]; }
		return a[1];
	}
	return b[0] + (b[1] - b[0]) * (cross(a[1]-a[0], a[1]-b[0]) / crs);
}

vector<Point> crosspoint(const Circle &c, const Line &l) {
	const Point p = project(l,c.c);
	const Real h = dist(p,c.c);

	vector<Point> res;
	if(sign(h - c.r) == 1) {
		//nothing
	}
	else if (sign(h - c.r) == 0) {
		res.emplace_back(p);
	}
	else {
		const Real b = sqrt(c.r*c.r - h*h);
		const Point e = (l[1] - l[0]) / abs(l[1] - l[0]);
		res.emplace_back(p+e*b);
		res.emplace_back(p-e*b);
	}

	return res;
}

//
bool contain(const Circle &c, const Point &p) {
	return sign(dist(c.c, p) - c.r) <= 0;
}


/*
 * Test Code
 */
int main() {
	//CCW=1, CW = -1, BACK= 2, FRONT=-2, ON=0
	int q;
	int cx,cy,r;

	cout.setf(ios::fixed);
	cout.precision(10); //?°???°???10?????¨???

	cin >> cx >> cy >> r;
	
	Circle c(Point(cx,cy),r);
	cin >> q;
	for(int i=0; i<q; i++) {
		Line l = Line(Point(),Point());
		cin >> l[0].x >> l[0].y >> l[1].x >> l[1].y;

		vector<Point> result = crosspoint(c, l);
		assert(!result.empty());
		sort(result.begin(), result.end());
		cout << result.front() << " " << result.back() << endl;
	}


	return EXIT_SUCCESS;
}