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<iomanip>
#include<string>
#include<algorithm>
#include<cmath>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) for(int i=0;i<(n);i++)
#define PII pair<int,int>
#define EPS (1e-10)
#define equals(a,b) (fabs((a)-(b))<EPS)
#define MP make_pair

class Point;
class Segment;
class circle;

class Point
{
public:
	double x, y;
	Point(double X = 0, double 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 *(const double a)const { return Point(x*a, y*a); };
	Point operator /(const double a)const { return Point(x / a, y / a); };
	double norm()const { return x*x + y*y; };
	double length()const { return sqrt(norm()); };
	double dot(const Point &p)const { return x*p.x + y*p.y; };
	double cross(const Point &p)const { return x*p.y - y*p.x; };
	Point normalize()const
	{
		Point ans(x, y);
		return ans = ans / ans.length();
	}
	bool operator ==(const Point &p)const
	{
		return fabs(x - p.x)<EPS &&fabs(y - p.y)<EPS;
	}
	friend ostream& operator <<(ostream& os, const Point &p);
	int CCW(Point p1, Point p2)
	{
		Point p0(x, y);
		Point V1 = p1 - p0;
		Point V2 = p2 - p0;
		if (V1.cross(V2) > 0.0)return -1;
		else if (V1.cross(V2) < 0.0)return 1;
		else if (V1.dot(V2) < 0.0)return -2;
		else if (V1.norm() < V2.norm())return 2;
		return 0;
	}
};
typedef Point Vector;

class Circle
{
public:
	Point c;
	double r;
	Circle(Point C = Point(), double R = 0)
	{
		c = C;
		r = R;
	}
};

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

class Segment
{
public:
	Point p1, p2;
	Segment(double x1, double y1, double x2, double y2)
	{
		p1.x = x1;
		p1.y = y1;
		p2.x = x2;
		p2.y = y2;
	}
	double GetLength()
	{
		Point temp = p2 - p1;
		return temp.length();
	}
	double GetDistanceSeg(double X, double Y)
	{
		Point p(X, Y);
		Point a = p2 - p1;
		Point b = p - p1;
		Point c = p1 - p2;
		Point d = p - p2;
		if (a.dot(b) < 0.0)return b.length();
		if (c.dot(d) < 0.0)return d.length();
		return GetDistanceLine(X, Y);
	}
	double GetDistanceLine(double X, double Y)
	{
		Point t(X, Y);
		Point a = p2 - p1;
		Point b = t - p1;
		return abs(a.cross(b) / a.length());
	}
	bool IsIntersect(Segment &s)
	{
		int s1, s2;
		s1 = p1.CCW(p2, s.p1)*p1.CCW(p2, s.p2);
		s2 = s.p1.CCW(s.p2, p1)*s.p1.CCW(s.p2, p2);
		return s1 <= 0 && s2 <= 0;
	}
	bool IsIntersect(Circle &Cir)
	{
		return GetDistanceLine(Cir.c.x, Cir.c.y) - Cir.r <= EPS;
	}
	bool IsOrthogonal(const Segment &s)
	{
		Vector t1 = p2 - p1;
		Vector t2 = s.p2 - s.p1;
		return equals(0.0, t1.dot(t2));
	}
	bool IsParallel(const Segment &s)
	{
		Vector t1 = p2 - p1;
		Vector t2 = s.p2 - s.p1;
		return equals(0.0, t1.cross(t2));
	}
	Point GetProjection(double X, double Y)const
	{
		Vector V = p2 - p1;
		Point P(X, Y);
		Point ret = V*(V.dot(P - p1) / V.norm());
		return ret + p1;
	}
	Point GetProjection(Point p)const
	{
		Vector V = p2 - p1;
		Point ret = V*(V.dot(p - p1) / V.norm());
		return ret + p1;
	}
	Point GetReflect(double X, double Y)
	{
		Point t(X, Y);
		Point Pro = GetProjection(X, Y);
		Vector dV = Pro - t;
		return t + dV*2.0;
	}
	Point GetCrossPoint(Segment &s)
	{
		Point P2 = p2 - p1;
		Point P3 = s.p1 - p1;
		Point P4 = s.p2 - p1;
		double d1 = abs(P2.cross(P3));
		double d2 = abs(P2.cross(P4));
		double t = d1 / (d1 + d2);
		Point ans = (P4 - P3)*t + P3 + p1;
		return ans;
	}
	pair<Point, Point> GetCrossPoint(Circle &Cir)
	{
		try { if (!IsIntersect(Cir)) { throw "error"; } }
		catch (string str) { cout << str << endl; }
		Vector pr = GetProjection(Cir.c);
		Vector p = (p2 - p1).normalize();
		double l = sqrt(Cir.r*Cir.r - (pr - Cir.c).norm());
		return make_pair(p*l + pr, p*(-l) + pr);
	}
};
typedef Segment Line;


int main()
{
	double x, y, r;
	cin >> x >> y >> r;
	Circle Cir(Point(x, y), r);
	int q;
	cin >> q;
	REP(i, q)
	{
		double x1, y1, x2, y2;
		cin >> x1>> y1>> x2>> y2;
		Segment s(x1, y1, x2, y2);
		pair<Point, Point> ans = s.GetCrossPoint(Cir);
		Point p1 = ans.first;
		Point p2 = ans.second;
		if (p1.x < p2.x)
		{
			cout << fixed << setprecision(10) << p1.x << " ";
			cout << fixed << setprecision(10) << p1.y << " ";
			cout << fixed << setprecision(10) << p2.x << " ";
			cout << fixed << setprecision(10) << p2.y << endl;
		}		
		else if (equals(p1.x, p2.x))
		{
			if (p1.y < p2.y)
			{
				cout << fixed << setprecision(10) << p1.x << " ";
				cout << fixed << setprecision(10) << p1.y << " ";
				cout << fixed << setprecision(10) << p2.x << " ";
				cout << fixed << setprecision(10) << p2.y << endl;
			}
			else
			{
				cout << fixed << setprecision(10) << p2.x << " ";
				cout << fixed << setprecision(10) << p2.y << " ";
				cout << fixed << setprecision(10) << p1.x << " ";
				cout << fixed << setprecision(10) << p1.y << endl;
			}
		}
		else
		{
			cout << fixed << setprecision(10) << p2.x << " ";
			cout << fixed << setprecision(10) << p2.y << " ";
			cout << fixed << setprecision(10) << p1.x << " ";
			cout << fixed << setprecision(10) << p1.y << endl;
		}
	}
	return 0;
}