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 r(i,n) for(int i=0;i<n;i++)
using namespace std;

#define EPS (1e-10)
#define equals(a,b) (fabs((a)-(b))<EPS)
//CCW??¨///////////////////////////////////
static const int COUNTER_CLOCKWISE = 1;
static const int CLOCKWISE = -1;
static const int ONLINE_BACK = 2;
static const int ONLINE_FRONT = -2;
static const int ON_SEGMENT = 0;
/////////////////////////////////////////
class Point{
  public:
  double x,y;
  Point(double x=0,double y=0):x(x),y(y){}
  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 a){return Point(a*x,a*y);}
  Point operator / (double a){return Point(x/a,y/a);}

  bool operator < (const Point &p) const{
    return x!=p.x?x<p.x:y<p.y;
  }
  bool operator == (const Point &p) const{
    return fabs(x-p.x)<EPS&&fabs(y-p.y)<EPS;
  }
};
struct Circle{
  Point c;
  double r;
};
typedef Point vect;
struct seg{Point p1,p2;};
//????????´?????????????????????
double norm(Point p){return p.x*p.x+p.y*p.y;}
//??¶????????????????????¬
double abs(Point p){return sqrt(norm(p));}
//?????????????????????????????????
double dot(Point a,Point b){
  return a.x*b.x+a.y*b.y;
}
//?????? ????????????????????????
double cross(Point a,Point b){
  return a.x*b.y-a.y*b.x;
}
//??´?????????????????¨?????\?????????????????????
bool C90(seg s1,seg s2){
  return equals(dot(s1.p2-s1.p1,s2.p2-s2.p1),0.0);
}
//????????????????????¨?????\??????????????????????????????????????????
bool C0(seg s1,seg s2){
  return equals(cross(s1.p2-s1.p1,s2.p2-s2.p1),0.0);
}
//?°???± ??????????????´???????????????
Point project(seg s,Point p){
  Point base = s.p2-s.p1;
  double r=dot(p-s.p1,base) / norm(base);
  return s.p1+base*r;
}
//????°????????????????????????????
Point reflection(seg s,Point p){
  return  p+(project(s,p)-p)*2.0;
}
//2???????????¢   ???????????????
double getDistancePP(Point a,Point b){
  return abs(a-b);
}
//??´??????????????¢(????°?)???????????????
double getDistanceLP(seg l,Point p){
  return abs(cross(l.p2-l.p1,p-l.p1)/abs(l.p2-l.p1));
}
//?????????????????¢??????????????????
double getDistanceSP(seg s,Point p){
  if(dot(s.p2-s.p1,p-s.p1)<0.0)return abs(p-s.p1);
  if(dot(s.p1-s.p2,p-s.p2)<0.0)return abs(p-s.p2);
  return getDistanceLP(s,p);
}
//????¨?????????????????¨??????????????????????????????????
int CCW(Point p0,Point p1,Point p2){
  Point a=p1-p0;
  Point b=p2-p0;
  if(cross(a,b)>EPS)return COUNTER_CLOCKWISE;
  if(cross(a,b)<-EPS)return CLOCKWISE;
  if(dot(a,b)<-EPS)return ONLINE_BACK;
  if(norm(a)<norm(b))return ONLINE_FRONT;
  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(seg s1,seg s2){
  return intersect(s1.p1,s1.p2,s2.p1,s2.p2);
}
//2??????????§???¢?????\??????????????????...????????????????????????
bool squareintersect(seg s1,seg s2){
  if(s1.p2.x<s2.p1.x||s2.p2.x<s1.p1.x)return 0;
  if(s1.p2.y<s2.p1.y||s2.p2.y<s1.p1.y)return 0;
  return 1;
}
//??????????????¢?????????????????????????????§??¨???????????????
double getDistance(seg s1,seg s2){
  if(intersect(s1,s2))return 0.0;
  return min(min(getDistanceSP(s1,s2.p1),getDistanceSP(s1,s2.p2)),
    min(getDistanceSP(s2,s1.p1),getDistanceSP(s2,s1.p2)));
}
//??????????????????????????????(?´????????`)
Point getCrossPoint(seg s1,seg s2){
  Point base=s2.p2-s2.p1;
  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.p2-s1.p1)*t;
}
//?????¨??´???????????????2??????
seg getCrossPoint(Circle c,seg l){
  //assert(intersect(cc,l));
  Point pr=project(l,c.c);
  Point e=(l.p2-l.p1)/abs(l.p2-l.p1);
  double base =sqrt(c.r*c.r-norm(pr-c.c));
  seg pp;pp.p1=(pr+e*base);pp.p2=(pr-e*base);
  return pp;
}
//????´???°2D///////////A???)///////////
typedef complex<double> comp;
typedef vector<comp> cvec;
//????´???????
double dot(comp a,comp b){return real(b*conj(a));}
//????´???????
double cross(comp a,comp b){return imag(b*conj(a));}
double Area(cvec &a){
  double b=0;int n=a.size();
  for(int i=0;i<n;i++)
    b+=cross(a[i],a[(i+1==n?0:i+1)]);
  return abs(b/2.0);
}
////how to use(exp)/////////////////////
//  double a,b; cvec t; cin>>n;       //
// while(n--){                        //
//    cin>>a>>b;                      //
//    t.push_back(comp(a,b));         //
//  }printf("%.11f\n",Area(t));       //
////////////////////////////////////////
seg scan(){
  seg a;
  scanf("%lf%lf%lf%lf",&a.p1.x,&a.p1.y,&a.p2.x,&a.p2.y);
  return a;
}

int main(){
  Circle o;
  cin>>o.c.x>>o.c.y>>o.r;
  int n;
  cin>>n;
  while(n--){
    seg a;
    a=scan();
    seg p=getCrossPoint(o,a);
    if(p.p1.x>p.p2.x){
      Point t;
      t=p.p1;
      p.p1=p.p2;
      p.p2=t;
    }
    else if(p.p1.x==p.p2.x&&p.p1.y>p.p2.y){
      Point t;
      t=p.p1;
      p.p1=p.p2;
      p.p2=t;
    }
    printf("%.9f %.9f %.9f %.9f\n",p.p1.x,p.p1.y,p.p2.x,p.p2.y);
  }
}