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;

typedef long long int ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pair<int, int> > vii;
#define rrep(i, m, n) for(int (i)=(m); (i)<(n);  (i)++)
#define erep(i, m, n) for(int (i)=(m); (i)<=(n); (i)++)
#define  rep(i, n)    for(int (i)=0; (i)<(n);  (i)++)
#define rrev(i, m, n) for(int (i)=(n)-1; (i)>=(m); (i)--)
#define erev(i, m, n) for(int (i)=(n); (i)>=(m); (i)--)
#define  rev(i, n)    for(int (i)=(n)-1; (i)>=0; (i)--)
#define vrep(i, c)    for(__typeof((c).begin())i=(c).begin(); i!=(c).end(); i++)
#define  ALL(v)       (v).begin(), (v).end()
#define pb            push_back
template<class T, class S> inline pair<T, S> mp(const T x, const S y){ return make_pair(x, y); }
template<class T, class S> inline bool minup(T& m, const S x){ return m>(T)x ? (m=(T)x, true) : false; }
template<class T, class S> inline bool maxup(T& m, const S x){ return m<(T)x ? (m=(T)x, true) : false; }

static const int    INF = 1000000000;
static const ll     MOD = 1000000007LL;
static const double EPS = 1E-10;

struct Point : public complex<double>
{
public:
  Point(const double x = 0.0, const double y = 0.0) { this->real(x);  this->imag(y); }
  Point(const complex<double> w)  { this->real(w.real());  this->imag(w.imag()); }
  inline double dot(Point p){ return (conj(*this) * p).real(); }  // 内積
  inline double det(Point p){ return (conj(*this) * p).imag(); }  // 外積
};

namespace std
{
  inline bool operator < (const Point& a, const Point& b)
  {
    return real(a) != real(b) ? real(a) < real(b) : imag(a) < imag(b);
  }
}
typedef vector<Point> Polygon;
inline Point currPoint(vector<Point> P, int i){ return P[i]; }
inline Point nextPoint(vector<Point> P, int i){ return P[(i+1)%P.size()]; }
inline Point diffPoint(vector<Point> P, int i){ return nextPoint(P, i) - currPoint(P, i); }


int ccw(Point a, Point b, Point c)
{
  b -= a;
  c -= a;
  if(b.det(c) > 0.0)    return  1;         // counter clockwise
  if(b.det(c) < 0.0)    return -1;         // clockwise
  if(b.dot(c) < 0.0)    return  2;         // c--a--b on line
  if(norm(b) < norm(c)) return -2;         // a--b--c on line
  return 0;
}


struct Line : public vector<Point>
{
public:
  Line(const Point P, const Point Q){ this->pb(P);  this->pb(Q); }
};

inline Point projectionOfLP(Line L, Point P){return L[0]+(Point(P-L[0])).dot(L[0]-L[1])/norm(L[0]-L[1])*(L[0]-L[1]);}
inline Point reflectionOfLP(Line L, Point P){return P+2.0*(projectionOfLP(L, P)-P);}
inline bool intersectionDeterminationOfLL(Line L, Line M){return abs(Point(L[1]-L[0]).det(M[1]-M[0]))>EPS||abs(Point(L[1]-L[0]).det(M[0]-L[0]))<EPS;}
inline bool intersectionDeterminationOfLS(Line L, Line S){return(Point(L[1]-L[0]).det(S[0]-L[0]))
*(Point(L[1]-L[0]).det(S[1]-L[0]))<EPS;}
inline bool intersectionDeterminationOfLP(Line L, Point P){return abs(Point(L[1]-P).det(L[0]-P))<EPS;}
inline bool intersectionDeterminationOfSS(Line S, Line T){return ccw(S[0],S[0],T[0])*ccw(S[0],S[1],T[1])<=0&&ccw(T[0],T[1],S[0])*ccw(T[0],T[1],S[1])<=0;}
inline bool intersectionDeterminationOfSP(Line S, Point P){return abs(S[0]-P)+abs(S[1]-P)-abs(S[1]-S[0])<EPS;}
inline double distanceOfLP(Line L, Point P){return abs(P-projectionOfLP(L,P));}
inline double distanceOfLL(Line L, Line M){return intersectionDeterminationOfLL(L,M)?0.0:distanceOfLP(L,M[0]);}
inline double distanceOfLS(Line L, Line S){return intersectionDeterminationOfLS(L,S)?0.0:min(distanceOfLP(L,S[0]),distanceOfLP(L,S[1]));}
inline double distanceOfSP(Line S, Point P){Point r=projectionOfLP(S,P);return intersectionDeterminationOfSP(S,r)?abs(r-P):min(abs(S[0]-P),abs(S[1]-P));}
inline double distanceOfSS(Line S, Line T){return intersectionDeterminationOfSS(S,T)?0.0:min(min(distanceOfSP(S,T[0]),distanceOfSP(S,T[1])),min(distanceOfSP(T,S[0]),distanceOfSP(T,S[1])));}
Point intersectionOfLL(Line L, Line M){
  double A = Point(L[1]-L[0]).det(M[1]-M[0]);
  double B = Point(L[1]-L[0]).det(L[1]-M[0]);
  if(abs(A)<EPS && abs(B)<EPS) return M[0];
  if(abs(A)<EPS) assert(false);
  return M[0] + B / A * (M[1] - M[0]);
}


struct Circle : Point
{
private:
  Point p;
  double r;

public:
  Circle(Point p, double r) : p(p), r(r) {}
  Circle(double x, double y, double r) : p(Point(x, y)), r(r) {}
  inline Point center(){ return this->p; }
  inline double radius(){ return this->r; }
};

// 円と直線との交点を重複を許して丁度２つ返す。交わらないときは直線と円の中心との距離で事前に判定
vector<Point> intersectionOfCL(Circle C, Line L)
{
  double r = C.radius();
  Point H = projectionOfLP(L, C.center());
  double d = abs(H - C.center());
  double l = sqrt(r * r - d * d);
  vector<Point> ret(2);
  Point v = (L[1] - L[0]) / abs(L[1] - L[0]);
  ret[0] = Point(H + l * v);
  ret[1] = Point(H - l * v);
  return ret;
}

double x, y, r;
int q;

int main()
{
  cin >> x >> y >> r;
  Circle C = Circle(x, y, r);

  cin >> q;
  while(q--){
    cin >> x >> y;
    Point A = Point(x, y);
    cin >> x >> y;
    Point B = Point(x, y);
    Line L = Line(A, B);
    vector<Point> res = intersectionOfCL(C, L);
    sort(ALL(res));
    printf("%.15f %.15f %.15f %.15f\n", res[0].real(), res[0].imag(), res[1].real(), res[1].imag());
  }

  return 0;
}