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:
/*
函数版本:0.3
*/
#include<iostream>
#include<stdio.h>
#include<math.h>
using namespace std;
#define EPS (1e-15)
#define equals(a,b) (fabs((a)-(b))<EPS)
#define COUNTER_CLOCKWISE 1
#define CLOCKWISE -1
#define ONLINE_BACK 2
#define ONLINE_FRONT -2
#define ON_SEGMENT 0


struct Segment;
class Point;
typedef Point Vector;
typedef Segment Line;

class Point {
public:
	double x, y;
	Point() {}
	Point(double xx, double yy) {
		x = xx;
		y = yy;
	}
	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 k) { return Point(x * k, y * k); }
	Point operator / (double k) { return Point(x / k, y / k); }

	double norm() { return x * x + y * y; }
	double abs() { return sqrt(norm()); }
	double dot(Point p) { return x * p.x + y * p.y; }
	double cross(Point& p) { return x * p.y - y * p.x; }
	double distance(Point& p) { return (*this - p).abs(); }

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

	void input() {
		cin >> x >> y;
	}
};

class Segment {
public:
	Point p1, p2;
	void input() {
		p1.input();
		p2.input();
	}
};

class Circle {
public:
	Point c;
	double r;
	void input() {
		c.input();
		cin >> r;
	}
};

double distance(Point p, Line s) {
	Vector a = s.p2 - s.p1;
	Vector b = p - s.p1;
	return a.cross(b) / a.abs();
}

double distanceS(Point p, Segment s) {
	Vector p1p = p - s.p1;
	Vector p2p = p - s.p2;
	Vector p1p2 = s.p2 - s.p1;
	Vector p2p1 = s.p1 - s.p2;
	if (p1p.dot(p1p2) < 0) {
		return p1p.abs();
	}
	else if (p2p.dot(p2p1) < 0) {
		return p2p.abs();
	}
	else {
		return distance(p, s);
	}
}

Point project(Point p, Segment s) {
	Vector hepo = p - s.p1;
	Vector base = s.p2 - s.p1;
	Vector t = base * (hepo.dot(base) / base.norm());
	return s.p1 + t;
}

int ccw(Point p0, Point p1, Point p) {
	Vector p0p1 = p1 - p0;
	Vector p0p;
	p0p = p - p0;
	if (p0p1.cross(p0p) > EPS) {
		return COUNTER_CLOCKWISE;
	}
	else if (p0p1.cross(p0p) < -EPS) {
		return CLOCKWISE;
	}
	else if (p0p1.dot(p0p) < -EPS) {
		return ONLINE_BACK;
	}
	else if (p0p1.norm() < p0p.norm()) {
		return ONLINE_FRONT;
	}
	else {
		return ON_SEGMENT;
	}
}

bool intersection(Segment s1, Segment s2) {
	Point p0 = s1.p1;
	Point p1 = s1.p2;
	Point p2 = s2.p1;
	Point p3 = s2.p2;
	return ccw(p0, p1, p2) * ccw(p0, p1, p3) <= 0 &&
		ccw(p2, p3, p0) * ccw(p2, p3, p1) <= 0;
}
Point getCrossPoint(Segment s1, Segment s2) {
	Point p1 = s1.p1;
	Point p2 = s1.p2;
	Point p3 = s2.p1;
	Point p4 = s2.p2;
	Vector p1_p2 = p2 - p1;
	Vector p1_p3 = p3 - p1;
	Vector p1_p4 = p4 - p1;
	Vector p4_p3 = p3 - p4;
	double d1 = fabs(p1_p2.cross(p1_p4)) / p1_p2.abs();
	double d2 = fabs(p1_p2.cross(p1_p3)) / p1_p2.abs();
	double r = d1 / (d1 + d2);
	Vector p4_p = p4_p3 * r;
	Point p = p4 + p4_p;
	return p;
}
pair<Point, Point> getCrossPoints(Circle circle, Line s) {
	Point p, p1, p2;
	Vector base, offset;
	double dis, d;
	p = project(circle.c, s);
	dis = distance(circle.c, s);
	base = s.p2 - s.p1;
	d = sqrt(circle.r * circle.r - dis * dis);
	offset = base / base.abs() * d;
	p1 = p + offset;
	p2 = p - offset;
	if (p1 < p2) {
		return make_pair(p1, p2);
	}
	else {
		return make_pair(p2, p1);
	}
}

int main() {
	Circle circle;
	Line s;
	int q;
	pair<Point, Point> p;

	circle.input();
	cin >> q;
	while (q--) {
		s.input();
		p = getCrossPoints(circle,s);
		printf("%.9lf %.9lf %.9lf %.9lf\n", p.first.x, p.first.y, p.second.x, p.second.y);
	}
}