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>
using namespace std;
const double eps=1e-9;
struct dot{
	double x,y;
	double len(){return sqrt(x*x+y*y);}
	dot(double a=0.0,double b=0.0){x=a,y=b;}
	dot operator +(const dot&b)const {return dot(x+b.x,y+b.y);}
	dot operator -(const dot&b)const {return dot(x-b.x,y-b.y);}
	dot operator *(const double&z)const {return dot(x*z,y*z);}
	bool operator <(const dot&b)const {return (y<b.y)||(y==b.y&&x<b.x);}
	bool operator ==(const dot&b)const {return fabs(x-b.x)<eps&&fabs(y-b.y)<eps;}	
	bool operator !=(const dot&b)const {return fabs(x-b.x)>=eps||fabs(y-b.y)>=eps;}
	void read(){scanf("%lf%lf",&x,&y);} 
};
struct line{
	dot x1,x2;
	void read(){x1.read();x2.read();};
	line(dot a=dot(0.0,0.0),dot b=dot(0.0,0.0)){x1=a,x2=b;} 
	dot getdot(){return x2-x1;}
};
double chaji(dot x,dot y){
	return x.x*y.y-x.y*y.x;
}
double neiji(dot x,dot y){
	return x.x*y.x+x.y*y.y;
}
double cos(dot x,dot y){
	if (!x.len()||!y.len())return 0;
	return neiji(x,y)/x.len()/y.len();
}
dot Projection(dot x,line y){//求x关于直线y的投影点（垂足） 
	y.x2=y.x2-y.x1;
	x=x-y.x1;
	double len=cos(x,y.x2)*x.len()/y.x2.len();
	y.x2=y.x2*len;
	return y.x2+y.x1;
}
dot Reflection(dot x,line y){//求x关于直线y的对称点 
	dot z=Projection(x,y);
	return z*2-x;
}
int Counter_Clockwise(dot x,line y){//求两个向量的五种关系 
	x=x-y.x1;y.x2=y.x2-y.x1;
	if (chaji(y.x2,x)!=0){
		if (chaji(y.x2,x)>0)return 1;
		return 2;
	} 
	if (fabs(cos(x,y.x2)+1)<eps)return 3;
	if (x.len()>y.x2.len())return 4;
	return 5;
} 
int Parallel_Orthogonal(line x,line y){//求两个直线是垂直还是平行还是其他 
	dot a=x.getdot(),b=y.getdot();
	if (chaji(a,b)==0)return 2;
	if (neiji(a,b)==0)return 1;
	return 0;
}
int Intersection(line x,line y){//求两条线段是否相交 
	int Minx1=min(x.x1.x,x.x2.x),Maxx1=max(x.x1.x,x.x2.x);
	int Minx2=min(y.x1.x,y.x2.x),Maxx2=max(y.x1.x,y.x2.x);
	int Miny1=min(x.x1.y,x.x2.y),Maxy1=max(x.x1.y,x.x2.y);
	int Miny2=min(y.x1.y,y.x2.y),Maxy2=max(y.x1.y,y.x2.y);
	if (Minx1>Maxx2||Minx2>Maxx1)return 0;
	if (Miny1>Maxy2||Miny2>Maxy1)return 0;
	if (chaji(x.getdot(),y.x1-x.x1)*chaji(x.getdot(),y.x2-x.x1)>0)return 0;
	if (chaji(y.getdot(),x.x1-y.x1)*chaji(y.getdot(),x.x2-y.x1)>0)return 0;
	return 1;
}
int Intersection2(line x,line y){//求线段和直线是否相交 
	if (chaji(y.getdot(),x.x1-y.x1)*chaji(y.getdot(),x.x2-y.x1)>0)return 0;
	return 1;
}
dot CrossPoint(line x,line y){//求两条线段的交点 
	if (fabs(cos(x.getdot(),y.getdot())-1)<eps||fabs(cos(x.getdot(),y.getdot())+1)<eps){
		if (x.x1<x.x2)swap(x.x1,x.x2);
		if (y.x1<y.x2)swap(y.x1,y.x2);
		if (x.x2<y.x2)return y.x2;
		else return x.x2;
	}
	else {
		if (x.x2.x-x.x1.x==0){
			double k2=(y.x2.y-y.x1.y)/(y.x2.x-y.x1.x),b2=y.x2.y-y.x2.x*k2;
			return dot(x.x2.x,x.x2.x*k2+b2);
		}
		if (y.x2.x-y.x1.x==0){
			double k1=(x.x2.y-x.x1.y)/(x.x2.x-x.x1.x),b1=x.x2.y-x.x2.x*k1;
			return dot(y.x2.x,y.x2.x*k1+b1);			
		}
		double k1=(x.x2.y-x.x1.y)/(x.x2.x-x.x1.x),b1=x.x2.y-x.x2.x*k1;
		double k2=(y.x2.y-y.x1.y)/(y.x2.x-y.x1.x),b2=y.x2.y-y.x2.x*k2;
		dot ans;
		ans.x=(b2-b1)/(k1-k2);ans.y=ans.x*k1+b1;
		return ans;
	}
} 
double Dis(dot x,dot y){//点到点的距离 
	return sqrt((x.x-y.x)*(x.x-y.x)+(x.y-y.y)*(x.y-y.y));
}
double dist(line x,dot y){//点到线段的距离 
	dot P=Projection(y,x);
	double k=neiji(x.getdot(),P-x.x1)/neiji(x.getdot(),x.getdot());
	if (k<=0)return Dis(x.x1,y);
	if (k>=1)return Dis(x.x2,y);
	return Dis(y,P);
}
double Distance(line x,line y){//线段之间距离 
	return min(min(dist(x,y.x1),dist(x,y.x2)),min(dist(y,x.x1),dist(y,x.x2)));
}
struct polygon{
	vector<dot > A;
	double S(){//多边形面积
		double ans=0;
		for (int i=0;i+1<A.size();i++)ans+=chaji(A[i],A[i+1])/2;
		if (A.size()>1)ans+=chaji(A[A.size()-1],A[0])/2;
		return ans;		
	}
	double C(){//多边形周长 
		double ans=0;
		for (int i=0;i+1<A.size();i++)ans+=Dis(A[i],A[i+1]);
		if (A.size()>1)ans+=Dis(A[A.size()-1],A[0]);
		return ans;
	}
	void read(){
		int n;scanf("%d",&n);A.resize(n);
		for (int i=0;i<n;i++)A[i].read();
	}
	int Is_Convex(){//是否是凸多边形 
		for (int i=0;i<A.size();i++)
			if (chaji(A[(i+1)%A.size()]-A[i],A[(i+2)%A.size()]-A[(i+1)%A.size()])<0)
				return 0;
		return 1;
	}
}G;
int PolygonPointContainment(polygon G,dot x){//射线和多边形的关系
	for (int i=0;i<G.A.size();i++)
		if (Counter_Clockwise(x,line(G.A[i],G.A[(i+1)%G.A.size()]))==5)return 1;
	for (int i=0;i<G.A.size();i++)
		if (x==G.A[i])return 1;
	double k=sqrt(2)+1,b=x.y-x.x*k;
	dot x2=dot(-1000000000,-1000000000*k+b);line R=line(x,x2);
	int ans=0;
	for (int i=0;i<G.A.size();i++)
		if (Intersection(R,line(G.A[i],G.A[(i+1)%G.A.size()])))ans++;
	if (ans&1)return 2;
	return 0;	
}
int isclock(dot x,dot y,dot z){//是否顺时针 
	return chaji(z-x,y-x)<0;
}
polygon Convex_Hull(polygon G){//求凸包 
	polygon ans1,ans2;
	sort(G.A.begin(),G.A.end());
	ans1.A.push_back(G.A[0]);ans1.A.push_back(G.A[1]);
	for (int i=2;i<G.A.size();i++){
		while (ans1.A.size()>=2&&isclock(ans1.A[ans1.A.size()-2],ans1.A[ans1.A.size()-1],G.A[i]))
			ans1.A.pop_back();
		ans1.A.push_back(G.A[i]);	
	}
	ans2.A.push_back(G.A[G.A.size()-1]);ans2.A.push_back(G.A[G.A.size()-2]);
	for (int i=G.A.size()-3;i>=0;i--){
		while (ans2.A.size()>=2&&isclock(ans2.A[ans2.A.size()-2],ans2.A[ans2.A.size()-1],G.A[i]))
			ans2.A.pop_back();
		ans2.A.push_back(G.A[i]);		
	}
	for (int i=1;i<ans2.A.size()-1;i++)ans1.A.push_back(ans2.A[i]);
	return ans1;
}
double DiameterofaConvexPolygon(polygon G){//求直径 
	int l=0,r=1,flag=1;
	double ans=Dis(G.A[0],G.A[1]);
	while (l!=0||flag){
		flag=0;
		while (Dis(G.A[l],G.A[r])<=Dis(G.A[l],G.A[(r+1)%G.A.size()])){
			r=(r+1)%G.A.size();
			ans=max(ans,Dis(G.A[l],G.A[r]));
		}
		l=(l+1)%G.A.size();
		ans=max(ans,Dis(G.A[l],G.A[r]));
	}
	return ans;
}
double Convex_Cut(polygon G,line x){//求多边形在线的左边的部分 
	polygon ans;line y=x;
	for (int i=0;i<G.A.size();i++){
		if (chaji(y.x2-y.x1,G.A[i]-y.x1)>=0)ans.A.push_back(G.A[i]);
		if (Intersection2(line(G.A[i],G.A[(i+1)%G.A.size()]),y))
			ans.A.push_back(CrossPoint(line(G.A[i],G.A[(i+1)%G.A.size()]),y));	
	}
	return ans.S();
}
int cmp2(int x,int y){
	return G.A[x]<G.A[y];
}
double ClosestPair(int l,int r){//求平面最近点对 
    double d=1e20;vector<int > ans;
    if (l==r)return d;
    if (l+1==r)return Dis(G.A[l],G.A[r]);
    int mid=(l+r)/2; 
    double d1=ClosestPair(l,mid),d2=ClosestPair(mid+1,r);
    d=min(d1,d2);
    for (int i=l;i<=r;i++)
        if (fabs(G.A[mid].x-G.A[i].x)<=d)ans.push_back(i);
    sort(ans.begin(),ans.end(),cmp2);
    for (int i=0;i<ans.size();i++)
        for (int j=i+1;j<ans.size()&&G.A[ans[j]].y-G.A[ans[i]].y<d;j++)
			d=min(d,Dis(G.A[ans[i]],G.A[ans[j]]));
    return d;
}
int cmp(dot x,dot y){
	return x.x<y.x||(x.x==y.x&&x.y<y.y);
}
struct cricle{
	dot x;
	int r;
	void read(){
		x.read();
		scanf("%d",&r);
	}
};
int IntersectionofCircles(cricle x,cricle y){//求两个圆的公切线个数 
	if (x.r+y.r<Dis(x.x,y.x))return 4;
	if (x.r+y.r==Dis(x.x,y.x))return 3;
	if (fabs(x.r-y.r)<Dis(x.x,y.x))return 2;
	if (fabs(x.r-y.r)==Dis(x.x,y.x))return 1;
	return 0;
}
line CrossPointsofaCirceandaLine(cricle x,line y){
	dot K=Projection(x.x,y);
	double p=sqrt(x.r*x.r-Dis(x.x,K)*Dis(x.x,K));
	line ans;y.x1=y.x1-K;y.x2=y.x2-K;
	ans.x1=(y.getdot())*(p/(y.getdot()).len())+K;
	ans.x2=(y.getdot())*(-p/(y.getdot()).len())+K;
	return ans;
}
int main(){
	cricle x;line y;
	x.read();int T;
	scanf("%d",&T);
	while (T--){
		y.read();
		line z=CrossPointsofaCirceandaLine(x,y);
		if (z.x1.x>z.x2.x||(z.x1.x==z.x2.x&&z.x1.y>z.x2.y))swap(z.x1,z.x2);
		printf("%.10lf %.10lf %.10lf %.10lf\n",z.x1.x,z.x1.y,z.x2.x,z.x2.y);
	}
}