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<cstdio>
#include<cstdlib>
#include<algorithm>
#include<vector>
#include<string>
#include<sstream>
#include<iomanip>
#include<utility>
#include<cmath>
#include<set>
using namespace std;
typedef long long int ll;
const double EPS=1e-10;

bool equals(double a,double b)
{
	return a>b?a-b<EPS:b-a<EPS;
}

class Point
{
public:
	double x;
	double y;
	Point(double inx=0.0,double iny=0.0):x(inx),y(iny){}
	Point operator+(const Point &p){return Point(x+p.x,y+p.y);}
	Point operator-(const Point &p){return Point(x-p.x,y-p.y);}
	Point operator*(const double k){return Point(x*k,y*k);}
	Point operator/(const double k){return Point(x/k,y/k);}
	Point operator=(const Point &p){x=p.x;y=p.y;return *this;}
	bool operator<(const Point &p)const{return x!=p.x?x<p.x:y<p.y;}
	bool operator==(const Point &p)const{return equals(x,p.x)&&equals(y,p.y);}
	double norm()
	{
		return x*x+y*y;
	}
	double abs()
	{
		return sqrt(norm());
	}
};

typedef Point Vector;

class Segment
{
public:
	Point p1;
	Point p2;
	Vector getvector()
	{
		return p2-p1;
	}
};

typedef Segment Line;

class Circle
{
public:
	Point c;
	double r;
	Circle(Point inc=Point(),double inr=0.0):c(inc),r(inr){}
};

typedef vector<Point> Polygon;

double dot(Vector a,Vector b)
{
	return a.x*b.x+a.y*b.y;
}

double cross(Vector a,Vector b)
{
	return a.x*b.y-a.y*b.x;
}
const int counter_clockwise=1;
const int clockwise=-1;
const int on_segment=0;
const int online_back=2;
const int online_front=-2;

double norm(Vector a)
{
	return a.x*a.x+a.y*a.y;
}

double abs(Vector a)
{
	return sqrt(norm(a));
}

bool isorthogonal(Vector a,Vector b)
{
	return equals(dot(a,b),0.0);
}

bool isorthogonal(Point a1,Point a2,Point b1,Point b2)
{
	return isorthogonal(a1-a2,b1-b2);
}

bool isorthogonal(Segment s1,Segment s2)
{
	return equals(dot(s1.getvector(),s2.getvector()),0.0);
}

bool isparallel(Vector a,Vector b)
{
	return equals(cross(a,b),0.0);
}

bool isparallel(Point a1,Point a2,Point b1,Point b2)
{
	return isparallel(a1-a2,b1-b2);
}

bool isparallel(Segment s1,Segment s2)
{
	return equals(cross(s1.getvector(),s2.getvector()),0.0);
}

Point project(Segment s,Point p)
{
	Vector base=s.getvector();
	double r=dot(p-s.p1,base)/norm(base);
	return s.p1+base*r;
}

Point reflect(Segment s,Point p)
{
	return project(s,p)*2.0-p;//p+(project(s,p)-p)*2.0
}

double getdistance(Point a,Point b)
{
	return abs(a-b);
}

double getdistancelp(Line l,Point p)//Line,Point
{
	double s=abs(cross(l.p2-l.p1,p-l.p1));
	return s/abs(l.getvector());
}

double getdistancesp(Segment s,Point p)
{
	if(dot(s.getvector(),p-s.p1)<0.0)return abs(p-s.p1);
	else if(dot(s.p1-s.p2,p-s.p2)<0.0)return abs(p-s.p2);
	else return getdistancelp(s,p);
}

int ccw(Point p0,Point p1,Point p2)
{
	Vector a=p1-p0;
	Vector b=p2-p0;
	if(cross(a,b)>EPS)return counter_clockwise;
	else if(cross(a,b)<-EPS)return clockwise;
	else if(dot(a,b)<-EPS)return online_back;
	else if(a.norm()<b.norm())return online_front;
	else return on_segment;
}

bool intersect(Point p1,Point p2,Point p3,Point p4)
{
	return ccw(p1,p2,p3)*ccw(p1,p2,p4)<=0&&ccw(p3,p4,p1)*ccw(p3,p4,p2)<=0;
}

bool intersect(Segment s1,Segment s2)
{
	return intersect(s1.p1,s1.p2,s2.p1,s2.p2);
}

double getdistance(Segment s1,Segment s2)
{
	if(intersect(s1,s2))return 0.0;
	else return min(min(getdistancesp(s1,s2.p1),getdistancesp(s1,s2.p2)),
			min(getdistancesp(s2,s1.p1),getdistancesp(s2,s1.p2)));
}

Point getcrosspoint(Segment s1,Segment s2)
{
	Vector base=s2.getvector();
	double d1=abs(cross(base,s1.p1-s2.p1));
	double d2=abs(cross(base,s1.p2-s2.p1));
	double t=d1/(d1+d2);
	return s1.p1+s1.getvector()*t;
}

pair<Point,Point> getcrosspoint(Circle c,Line l)
{
	Vector pr=project(l,c.c);
	Vector e=l.getvector()/abs(l.getvector());
	double base=sqrt(c.r*c.r-norm(pr-c.c));
	return make_pair(pr+e*base,pr-e*base);
}

double arg(Vector p)
{
	return atan2(p.y,p.x);
}

Point polar(double r,double theta)
{
	return Point(r*cos(theta),r*sin(theta));
}

pair<Point,Point> getcrosspoint(Circle c1,Circle c2)
{
	double d=abs(c2.c-c1.c);
	double a=acos((c1.r*c1.r+d*d-c2.r*c2.r)/(2.0*c1.r*d));
	double t=arg(c2.c-c1.c);
	return make_pair(c1.c+polar(c1.r,t+a),c1.c+polar(c1.r,t-a));
}
const int Bottom=0;
const int Left=1;
const int Right=2;
const int Top=3;

class endPoint
{
public:
	Point p;
	int seg;//id of Point
	int st;//kind of Point
	endPoint(){}
	endPoint(Point inp,int inseg,int inst):p(inp),seg(inseg),st(inst){}
	bool operator<(const endPoint &ep)const
	{
		if(p.y==ep.p.y)
		{
			return st<ep.st;//Bottom->Left->Right->Top
		}
		else return p.y<ep.p.y;
	}
};

endPoint EP[200000];

int manhattanintersection(vector<Segment> s)
{
	int n=s.size();
	double sto;
	
	for(int i=0,k=0;i<n;i++)
	{
		if(s[i].p1.y==s[i].p2.y)
		{
			if(s[i].p1.x>s[i].p2.x)
			{
				sto=s[i].p1.x;
				s[i].p1.x=s[i].p2.x;
				s[i].p2.x=sto;
			}
		}
		else if(s[i].p1.y>s[i].p2.y)
		{
			sto=s[i].p1.y;
			s[i].p1.y=s[i].p2.y;
			s[i].p2.y=sto;
		}
		
		if(s[i].p1.y==s[i].p2.y)
		{
			EP[k++]=endPoint(s[i].p1,i,Left);
			EP[k++]=endPoint(s[i].p2,i,Right);
		}
		else
		{
			EP[k++]=endPoint(s[i].p1,i,Bottom);
			EP[k++]=endPoint(s[i].p2,i,Top);
		}
	}
	
	sort(EP,EP+2*n);
	
	set<int> BT;
	BT.insert(1000000001);
	int cnt=0;
	
	for(int i=0;i<2*n;i++)
	{
		if(EP[i].st==Top)BT.erase(EP[i].p.x);
		else if(EP[i].st==Bottom)BT.insert(EP[i].p.x);
		else if(EP[i].st==Left)
		{
			set<int>::iterator b=lower_bound(BT.begin(),BT.end(),s[EP[i].seg].p1.x);
			set<int>::iterator e=upper_bound(BT.begin(),BT.end(),s[EP[i].seg].p2.x);
			cnt+=distance(b,e);
		}
	}
	
	return cnt;
}
Polygon andrewscan(Polygon s)
{
	Polygon u,l;
	if(s.size()<=2)return s;
	sort(s.begin(),s.end());
	u.push_back(s[0]);
	u.push_back(s[1]);
	l.push_back(s[s.size()-1]);
	l.push_back(s[s.size()-2]);
	
	for(int i=2;i<s.size();i++)
	{
		for(int n=u.size();n>=2&&ccw(u[n-2],u[n-1],s[i])!=clockwise;n--)
		{
			u.pop_back();
		}
		u.push_back(s[i]);
	}
	
	for(int i=s.size()-3;i>=0;i--)
	{
		for(int n=l.size();n>=2&&ccw(l[n-2],l[n-1],s[i])!=clockwise;n--)
		{
			l.pop_back();
		}
		l.push_back(s[i]);
	}
	
	reverse(l.begin(),l.end());
	for(int i=u.size()-2;i>=1;i--)l.push_back(u[i]);
	
	return l;
}
const int in=2;
const int on=1;
const int out=0;

int contain(Polygon g,Point p)
{
	int n=g.size();
	bool x=false;
	Point a,b;
	for(int i=0;i<n;i++)
	{
		a=g[i]-p;
		b=g[(i+1)%n]-p;
		if(abs(cross(a,b))<EPS&&dot(a,b)<EPS)return on;
		if(a.y>b.y)
		{
			Point sto=a;
			a=b;
			b=sto;
		}
		if(a.y<EPS&&EPS<b.y&&cross(a,b)>EPS)x=!x;
	}
	return x?in:out;
}
int main()
{
	Circle c;
	cin>>c.c.x>>c.c.y>>c.r;
	int q;cin>>q;
	Segment s1;
	pair<Point,Point>a;
	for(int i=0;i<q;i++)
	{
		cin>>s1.p1.x>>s1.p1.y>>s1.p2.x>>s1.p2.y;
		a=getcrosspoint(c,s1);
		if(a.first<a.second)cout<<fixed<<setprecision(8)<<a.first.x<<" "<<a.first.y<<" "<<a.second.x<<" "<<a.second.y<<endl;
		else cout<<fixed<<setprecision(8)<<a.second.x<<" "<<a.second.y<<" "<<a.first.x<<" "<<a.first.y<<endl;
	}
	return 0;	
}