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 <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <sstream>
#include <map>
#include <set>
#include <cmath>

#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1<<30
#define pb push_back
#define mp make_pair
#define EPS 1e-8
#define equals(a,b) fabs((a) - (b)) < EPS

using namespace std;
typedef long long ll;
typedef pair<int,int> P;

struct Point {
	double x, y;

	Point(double x=0, double y=0) : x(x), y(y) {}

	Point operator+(const Point &o) const { return Point(x+o.x, y+o.y); }

	Point operator-(const Point &o) const { return Point(x-o.x, y-o.y); }

	Point operator*(const double m) const { return Point(x*m, y*m); }

	Point operator/(const double d) const { return Point(x/d, y/d); }

	bool operator<(const Point &o) const { return x != o.x ? x < o.x : y < o.y; }

	bool operator==(const Point &o) const { return fabs(x-o.x) < EPS && fabs(y-o.y) < EPS; }
};

ostream& operator << (ostream& os, const Point& p) {
	os << "(" << p.x << ", " << p.y << ")";
	return os;
}

double dot(Point a, Point b) { return a.x * b.x + a.y * b.y; }
double cross(Point a, Point b) { return a.x * b.y - a.y * b.x; }
double atan(Point p) { return atan2(p.y, p.x); }
double norm(Point p) { return p.x * p.x + p.y * p.y; }
double abs(Point p) { return sqrt(norm(p)); }
double distancePP(Point p, Point o) { return sqrt(norm(o - p)); }

int ccw(Point a, Point b, Point c) {
	b = b-a;
	c = c-a;

	if(cross(b, c) > 0.0) return +1;	//conter clockwise
	if(cross(b, c) < 0.0) return -1;	//clockwise
	if(dot(b, c) < 0.0) return +2;	//a on Seg(b,c)
	if(norm(b) < norm(c)) return -2;	//b on Seg(a,c)
	return 0;	//c on Seg(a,b)
}

struct Line {
	Point a, b;

	Line() : a(Point(0, 0)), b(Point(0, 0)) {}

	Line(Point a, Point b) : a(a), b(b) {}
};

ostream& operator << (ostream& os, const Line& l) {
	os << "(" << l.a.x << ", " << l.a.y << ")-(" << l.b.x << "," << l.b.y << ")";
	return os;
}

struct Seg {
	Point a,b;

	Seg() : a(Point(0, 0)), b(Point(0, 0)) {}

	Seg (Point a, Point b) : a(a),b(b) {}
};

ostream& operator << (ostream& os, const Seg& s) {
	os << "(" << s.a.x << ", " << s.a.y << ")-(" << s.b.x << "," << s.b.y << ")";
	return os;
}

bool isOrthogonal(Line l1, Line l2) { return equals(dot((l1.b - l1.a), (l2.b - l2.a)), 0.0); }

bool isParallel(Line l1, Line l2) { return equals(cross((l1.b - l1.a), (l2.b - l2.a)), 0.0); }

bool sameLine(Line l1, Line l2) { return abs(cross(l1.b - l1.a, l2.b - l1.a)) < EPS; }

bool isIntersectLL(Line l1, Line l2) { return !isParallel(l1, l2) || sameLine(l1, l2); }

bool isIntersectLS(Line l, Seg s) {
	return cross(l.b - l.a, s.a - l.a) * cross(l.b - l.a, s.b - l.a) < 0;
}

bool isIntersectSS(Seg s1, Seg s2) { 
	return ccw(s1.a, s1.b, s2.a) * ccw(s1.a, s1.b, s2.b) <= 0 
		&& ccw(s2.a, s2.b, s1.a) * ccw(s2.a, s2.b, s1.b) <= 0;
}

double distanceLP(Line l, Point p) {
	return abs(cross(l.b - l.a, p - l.a)) / abs(l.b - l.a);
}

double distanceLS(Line l, Seg s) {
	if (isIntersectLS(l, s)) return 0.0;
	return min(distanceLP(l, s.a), distanceLP(l, s.b));
}

double distanceSP(Seg s, Point p) {
	if (dot(s.b - s.a, p - s.a) < 0.0) return abs(p - s.a);
	if (dot(s.a - s.b, p - s.b) < 0.0) return abs(p - s.b);
	return distanceLP(Line(s.a, s.b) , p);
}

double distanceSS(Seg s1, Seg s2) {
	if (isIntersectSS(s1, s2)) return 0.0;
	return min( min(distanceSP(s1, s2.a), distanceSP(s1, s2.b)), min(distanceSP(s2, s1.a), distanceSP(s2, s1.b)) );
}

// if isIntersectLL(l1, l2)
Point crossPointLL(Line l1, Line l2) {
	Point base = l2.b - l2.a;
	double d = abs(cross(base, l1.a - l2.a));
	double d2 = abs(cross(base, l1.b - l2.a));
	double t = d / (d + d2);
	return l1.a + (l1.b - l1.a) * t;
}

// if isIntersectLS(l, s)
Point crossPointLS(Line l, Seg s) { return crossPointLL(l, Line(s.a, s.b)); }

// if isIntersectSS(s1, s2)
Point crossPointSS(Seg s1, Seg s2) { return crossPointLL(Line(s1.a, s1.b), Line(s2.a, s2.b)); }

Point project(Line l, Point p) {
	Point base = l.b - l.a;
	double t = dot(base, p-l.a) / dot(base, base);
	return l.a + base * t;
}

Point reflect(Line l, Point p) {
	return p + (project(l, p) - p) * 2.0;
}

struct Circle {
	Point p;
	double r;

	Circle() : p(Point(0,0)), r(0) {}

	Circle(Point o, double r) : p(o), r(r) {}

	Circle(double x, double y, double r) : p(Point(x, y)), r(r) {}
};

bool inCircle(Circle c, Point p) {
	Point a = p - c.p;
	return dot(a, a) <= c.r * c.r + EPS;
}

bool isIntersectCL(Circle c, Line l) {
	return distanceLP(l, c.p) <= c.r + EPS;
}

// 1:?????§??\?????????0:???????????????-1:?????§??\?????????2:?????????-2:??????
int isIntersectCC(Circle c1, Circle c2) {
	double d = dot(c2.p - c1.p, c2.p - c1.p);
	double len = (c1.r + c2.r) * (c1.r + c2.r);

	if(equals(d, len)) return 1;
	if(d > len) return 0;

	double R = fabs(c2.r - c1.r) * fabs(c2.r - c1.r);
	if(equals(d, R)) return -1;
	if(d > R) return 2;
	return -2;
}

// isIntersectCL
vector<Point> crossPointCL(Circle c, Line l) {
	Point p = project(l, c.p);
	Point base = (l.b - l.a) / abs(l.b - l.a);
	double t = sqrt(c.r * c.r - norm(p - c.p) );
	vector<Point> ret(2);
	ret[0] = p + base * t;
	ret[1] = p - base * t;
	return ret;
}

vector<Point> crossPointCC(Circle c1, Circle c2) {
	vector<Point> ret;
	int ch = isIntersectCC(c1, c2);

	if(ch == 0 || ch == -2) return ret;

	Point base = c2.p - c1.p;
	double len = dot(base, base);
	double t = (c1.r*c1.r - c2.r*c2.r + len) / (2.0 * len);

	if(ch == 2) {
		Point n(-base.y, base.x);
		n = n / (abs(n));
		double h = sqrt(c1.r * c1.r - t * t * len);

		ret.push_back(c1.p + (base*t) + (n*h));
		ret.push_back(c1.p + (base*t) - (n*h));
	} else {
		ret.push_back(c1.p + (base*t));
	}

	return ret;
}

int main() {
	Circle c1;
	cin >> c1.p.x >> c1.p.y >> c1.r;

	int q;
	cin >> q;

	Line l;
	rep(i, q) {
		cin >> l.a.x >> l.a.y >> l.b.x >> l.b.y;

		vector<Point> ret = crossPointCL(c1, l);
		sort(ret.begin(), ret.end());

		cout << fixed;
		cout.precision(20);
		cout << ret[0].x << " " << ret[0].y << " " << ret[1].x << " " << ret[1].y << endl;
	}

	return 0;
}