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<iostream>
#include<map>
#include<climits>
#include<ctime>
#include<cstring>
#include<numeric>

#include<algorithm>
#include<array>
#include<cassert>
#include<cmath>
#include<vector>

#define ALL(v) (v).begin(),(v).end()
#define REP(i,p,n) for(int i=p;i<(int)(n);++i)
#define rep(i,n) REP(i,0,n)
#define dump(a) (cerr << #a << "=" << (a) << endl)
#define DUMP(list) cout << "{ "; for(auto nth : list){ cout << nth << " "; } cout << "}" << endl;

using namespace std;

typedef double Real;
const Real EPS = 1e-8;
int sign(Real d) { return d > EPS ? 1 : d < -EPS ? -1 : 0; }

//define class ...

struct Point {
	Real x, y;
	explicit Point(Real x_ = 0, Real y_ = 0):x(x_), y(y_) {}
	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;
	}
};

istream &operator>>(istream &is, Point &p) {
	return is >> p.x >> p.y;
}

ostream &operator<<(ostream &os, Point &p) {
	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;

// define function
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);
}

Real angle(const Point &p) {
	return atan2(p.y, p.x);
}

Real norm(const Point &p) {
	return p.x * p.x + p.y * p.y;
}

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;
}

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

// define app function
enum { CCW = 1, CW = -1, BACK = 2, FRONT = -2, ON = 0};

int ccw(const Point &a, const Point &b, const Point &c) {
	const Point p = b - a;
	const Point q = c - a;
	const Real crs = cross(p, q); 
	
	if(sign(crs) == 1) return CCW;
	if(sign(crs) == -1) return CW;
	if(sign(dot(p, q)) == -1) return BACK;
	if(sign(norm(p) - norm(q)) == -1) return FRONT;
	return ON;
}

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);
}

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) {
	const Point a = l[1] - l[0];
	const 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, const Segment &s) {
	return sign(dist(s, c.c) - c.r) <= 0;
}

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

bool contain(const Circle &c, const Point &p) {
	return sign(dist(c.c, p) - 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];	// same line
	return b[0] + (b[1] - b[0]) * (cross(a[1] - a[0], a[1] - b[0]) / crs);
}

// ???????????????????????¨?????°????????§???????????????intersect????????????
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) { //on same line
		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;
}

int main() {
	cout.setf(ios::fixed);
	cout.precision(10);
	Point c;
	Real r;
	int q;	
	cin >> c >> r;	
	cin >> q;	
	rep(i, q) {
		Point p1, p2;
		cin >> p1 >> p2;
		vector<Point> ans = crosspoint(Circle(c, r), Line(p1, p2));	
		sort(ALL(ans));
		cout << ans.front().x << " " << ans.front().y << " " << ans.back().x << " " << ans.back().y << endl; 
	}

	return 0;
}