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>
#define cmin(a,b) (a>(b)?a=(b),1:0)
#define cmax(a,b) (a<(b)?a=(b),1:0)
#define dmin(a,b) ((a)<(b)?(a):(b))
#define dmax(a,b) ((a)>(b)?(a):(b))
namespace io
{
	int F()
	{
		 int F=1,n=0;
		 char ch;
		 while((ch=getchar())!='-'&&(ch<'0'||ch>'9'));
		 ch=='-'?F=0:n=ch-'0';
		 while((ch=getchar())>='0'&&ch<='9')n=n*10+ch-'0';
		 return F?n:-n;
	}
	long long G()
	{
		 long long F=1,n=0;
		 char ch;
		 while((ch=getchar())!='-'&&(ch<'0'||ch>'9'));
		 ch=='-'?F=0:n=ch-'0';
		 while((ch=getchar())>='0'&&ch<='9')n=n*10+ch-'0';
		 return F?n:-n;
	}
}
namespace Geometry
{
	typedef double Scalar;
	
	Scalar Abs(Scalar x) {
		return x > 0 ? x : -x;
	}
	
	const Scalar eps = 1e-12;
	
	const double pi = acos(-1);
	
	struct Point;
	typedef Point Vector;
	
	struct Point
	{
		Scalar x,y;
		Scalar len() const {
			return sqrt(x*x + y*y);
		}
		Scalar len2() const {
			return x * x + y * y;
		}
        Vector uni() const {
            Scalar l = len();
            return (Vector){x / l, y / l};
        }
		Point operator + (const Vector &b) const {
			return (Point){x + b.x, y + b.y};
		}
		Vector operator - (const Point &b) const {
			return (Vector){x - b.x, y - b.y};
		}
		Point rotate(double ang) const {
			return (Point){x * cos(ang) - y * sin(ang), x * sin(ang) + y * cos(ang)};
		}
		Point rotate(const Point &o, double ang) const {
			return (*this - o).rotate(ang) + o;
		}
		void print() {
			printf("(%.3lf,%.3lf)\n",(double)x,(double)y);
		}
	};
	
	bool operator == (const Point &x, const Point &y) {
		return Abs(x.x - y.x) <= eps && Abs(x.y - y.y) <= eps;
	}
	Scalar operator * (const Vector &x, const Vector &y) {
		return x.x * y.y - x.y * y.x;
	}
	Scalar operator / (const Vector &x, const Vector &y) {
		return x.x * y.x + x.y * y.y;
	}
	Vector operator * (const Scalar &x, const Vector &y) {
		return (Vector){x * y.x, x * y.y};
	}
	Vector operator * (const Vector &y, const Scalar &x) {
		return (Vector){x * y.x, x * y.y};
	}
	Vector operator / (const Vector &x, const Scalar &y) {
		return (Vector){x.x / y, x.y / y};
	}
	
	struct Line
	{
		Point o;
		Vector l; // unit length
	};
	
	Scalar dist(const Point &x, const Line &y) { //signed
		return y.l * (x - y.o);
	}
	
	Point footpoint(const Point &x, const Line &y) {
		Scalar d=dist(x,y);
		return x - d * y.l.rotate(pi / 2);
	}
	
	Point intersect(const Line &x, const Line &y) {
		Scalar d1 = dist(x.o, y);
		Scalar d2 = dist(x.o + x.l, y);
		return x.o + d1 / (d1 - d2) * x.l;
	}
	
	struct Seg
	{
		Point x,y;
		Scalar len() const {
			return (x - y).len();
		}
	};
	
	Line line(const Seg &x) {
		return (Line){x.x, (x.y - x.x) / x.len()};
	}
	
	Scalar dist(const Point &o, const Seg &l) {
		if(Abs((l.y - l.x) * (o - l.x)) <= eps)
		{
			Scalar d1 = (o - l.x).len();
			Scalar d2 = (o - l.y).len();
			return (Abs(d1 + d2 - l.len()) <= eps) ? 0 : std::min(d1, d2);
		}
		else
		{
			if((l.y - l.x) / (o - l.x) < 0) return (o - l.x).len();
			if((l.x - l.y) / (o - l.y) < 0) return (o - l.y).len();
			return dist(o, line(l));
		} 
	}
	
	int convexHull(Point *p, int n, Point *s) { // return # of points on the convex hull + 1
		std::sort(p + 1, p + n + 1, [](const Point &x, const Point &y)  { return x.x != y.x ? x.x < y.x : x.y < y.y;});
		int ts;
		for(int i = 1; i <= n; ++i)
			if(i == 1 || !(p[i] == p[i-1]))
			{
				while(ts > 1 && (p[i] - s[ts-1]) * (s[ts] - s[ts-1]) <= 0)
					--ts;
				s[++ts] = p[i];
			}
		int cl = ts;
		for(int i = n - 1; i; ++i)
			if(!(p[i] == p[i+1]))
			{
				while(ts > cl && (p[i] - s[ts-1]) * (s[ts] - s[ts-1]) <= 0)
					--ts;
				s[++ts] = p[i];
			}
		return ts;
	}
	
	struct Circle
	{
		Point o;
		Scalar r;
	};
	
	std::pair<Point, Point> intersect(const Circle &c, const Line &l) {
		Scalar d = dist(c.o, l);
		Point p = footpoint(c.o, l);
		Scalar k = c.r * c.r - (c.o - p).len2();
		k = k < 0 ? 0 : sqrt(k);
		return std::make_pair(p + k * l.l, p - k * l.l);
	}
	
	std::pair<Point, Point> intersect(const Circle &x, const Circle &y) {
		Scalar d = (x.o - y.o).len();
		double ang = acos((x.r * x.r + d * d - y.r * y.r)/(2 * x.r * d));
		Vector v = x.r * (y.o - x.o) / d;
		return std::make_pair(x.o + v.rotate(ang), x.o + v.rotate(-ang));
	}
	
	std::pair<Line, Line> tangentLine(const Point &x, const Circle &c) {
		if(Abs((x - c.o).len() - c.r) <= eps) {
			Line l = (Line){x, (x - c.o).uni().rotate(pi/2)};
			return std::make_pair(l,l);
		}
		Scalar d1 = (c.o - x).len();
		double ang = asin(c.r / d1);
		Vector v = (c.o - x).uni();
		return std::make_pair((Line){x, v.rotate(ang)}, (Line){x, v.rotate(-ang)});
	}
	
	std::pair<Point, Point> tangentPoint(const Point &x, const Circle &c) {
		auto tl = tangentLine(x, c);
		Scalar d1 = (c.o - x).len();
		double ang = asin(c.r / d1);
		Scalar d2 = d1 * cos(ang);
		return std::make_pair(x + d2 * tl.first.l, x + d2 * tl.second.l);
	}
	
	std::pair<Line, Line> outerTLine(Circle x, Circle y) {
		if(x.r > y.r)std::swap(x, y);
		y.r -= x.r;
		auto p = tangentPoint(x.o, y);
		auto l = tangentLine(x.o, y);
		l.first.o = l.first.o + (p.first - y.o).uni() * (y.r + x.r) - (p.first - y.o);
		l.second.o = l.second.o + (p.second - y.o).uni() * (y.r + x.r) - (p.first - y.o);
		return l;
	}
	
	std::pair<Line, Line> innerTLine(const Circle &x, Circle y) {
		y.r += x.r;
		auto p = tangentPoint(x.o, y);
		auto l = tangentLine(x.o, y);
		l.first.o = l.first.o + (p.first - y.o).uni() * (y.r - x.r) - (p.first - y.o);
		l.second.o = l.second.o + (p.second - y.o).uni() * (y.r - x.r) - (p.first - y.o);
		return l;
	} 
	bool operator <(const Point &x,const Point &y)
	{
	    if(fabs(x.x-y.x)>1e-8)return x.x<y.x;
	    return x.y<y.y;
	}
}
int main()
{
    int cx=io::F(),cy=io::F(),r=io::F();
    using namespace Geometry;
    Circle c={(Point){(double)cx,(double)cy},(double)r};
    int q=io::F();
    while(q--)
    {
        int x1=io::F(),y1=io::F(),x2=io::F(),y2=io::F();
        Point p1=(Point){(double)x1,(double)y1},p2=(Point){(double)x2,(double)y2};
        Line l=line((Seg){p1,p2});
        auto s=intersect(c,l);
        if(s.second<s.first)std::swap(s.first,s.second);
        printf("%.9lf %.9lf %.9lf %.9lf\n",s.first.x,s.first.y,s.second.x,s.second.y);
    }
	return 0;
}