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 ll;
#define REP(i,n) for(int i=0,_n=(int)(n);i<_n;++i)
#define ALL(v) (v).begin(),(v).end()
#define CLR(t,v) memset(t,(v),sizeof(t))
template<class T1,class T2>ostream& operator<<(ostream& os,const pair<T1,T2>&a){return os<<"("<<a.first<<","<<a.second<< ")";}
template<class T>void pv(T a,T b){for(T i=a;i!=b;++i)cout<<(*i)<<" ";cout<<endl;}
template<class T>void chmin(T&a,const T&b){if(a>b)a=b;}
template<class T>void chmax(T&a,const T&b){if(a<b)a=b;}


typedef double D;
const D PI = acos(-1.0);
const D EPS = 1e-10;
struct P {
  D x, y;
  P(D x=0, D y=0) : x(x), y(y) {}

  P& operator+=(const P& o) { x += o.x; y += o.y; return *this; }
  P& operator-=(const P& o) { x -= o.x; y -= o.y; return *this; }
  P& operator*=(const P& o) { return *this = {x*o.x - y*o.y, x*o.y + y*o.x}; }
  P& operator*=(const D& r) { x *= r; y *= r; return *this; }
  P& operator/=(const D& r) { x /= r; y /= r; return *this; }
  P operator-() const { return {-x, -y}; }

  D norm() const { return x*x + y*y; }
  D abs() const { return sqrt(norm()); }
  D arg() const { return atan2(y, x); }
  bool isZero() const { return std::abs(x) < EPS && std::abs(y) < EPS; }
  /** 象限 */
  int orth() const { return y >= 0 ? (x >= 0 ? 1 : 2) : (x < 0 ? 3 : 4); }
  static P polar(const D& rho, const D& theta = 0) { return {rho * cos(theta), rho * sin(theta)}; }
};
std::ostream &operator<<(std::ostream &os, P const &p) { return os << "(" << p.x << ", " << p.y << ")"; }
std::istream &operator>>(std::istream &is, P &p) { D a, b; is >> a >> b; p = P(a, b); return is; }
P operator+(const P& p, const P& q) { return P(p) += q; }
P operator-(const P& p, const P& q) { return P(p) -= q; }
P operator*(const P& p, const P& q) { return P(p) *= q; }
P operator*(const P& p, const D& r) { return P(p) *= r; }
P operator/(const P& p, const D& r) { return P(p) /= r; }
P operator*(const D& r, const P& p) { return P(p) *= r; }
P operator/(const D& r, const P& p) { return P(p) /= r; }
D crs(const P& a, const P& b){ return a.x*b.y - a.y*b.x; }
D dot(const P& a, const P& b){ return a.x*b.x + a.y*b.y; }
int signum(D x) {return x > EPS ? +1 : x < -EPS ? -1 : 0;}
bool operator<(const P& a, const P& b) {
  if (a.x != b.x) return a.x < b.x;
  return a.y < b.y;
}

/** ベクトルpをベクトルbに射影したベクトル */
P proj(const P& p, const P& b) {
  P t = b * dot(p, b);
  return t / b.norm();
}
/** 点pから直線abに引いた垂線の足となる点 */
P footOfLP(const P& a, const P& b, const P& p) {
  return a + proj(p-a, b-a);
}

double distLP(const P& a, const P& b, const P& c) {
  return abs(crs(b-a, c-a)) / (b-a).abs();
}

int ccw(const P& a, P b, P c) {
  // return signum(crs(b - a, c - a));
  b -= a; c -= a;
  if (crs(b, c) > 0)       return +1;       // counter clockwise
  if (crs(b, c) < 0)       return -1;       // clockwise
  if (dot(b, c) < 0)       return +2;       // c--a--b on line
  if (b.norm() < c.norm()) return -2;       // a--b--c on line
  return 0;
}
P intersectionLL(const P& a1, const P& a2, const P& b1, const P& b2){
  P a = a2 - a1; P b = b2 - b1;
  return a1 + a * crs(b, b1-a1) / crs(b, a);
}
// 凸多角形をある直線で切断し、左側を残す。
// 凸多角形は半時計回りに与えられていること
vector<P> convexCut(const vector<P>& ps, const P& p1, const P& p2) {
  vector<P> ret;
  int N = ps.size();
  REP(i,N){
      P a = ps[i];
      P b = ps[(i+1)%N];
      if( ccw(p1, p2, a) != -1 ) ret.push_back(a);
      if( ccw(p1, p2, a) * ccw(p1, p2, b) == -1 )
          ret.push_back( intersectionLL(a,b,p1,p2) );
  }
  return ret;
}
 double area(const vector<P> &v) {
  double ret = 0.0;
  REP(i, v.size()) ret += crs(v[i], v[(i+1) % v.size()]);
  return abs(ret / 2.0);
}

struct C : public P {
  D r;
  C() {}
  C(const P &p, D r):P(p),r(r){}
};

// 直線abと円cの交点をvectorで返す
vector<P> intersectionLC(const P& a, const P& b, const C& c){
  double dist = distLP(a,b,c);
  vector<P> ret;
  if( abs(dist - c.r) < EPS ) {
    ret.push_back( footOfLP(a,b,c) );
  } else if( dist < c.r ) {
    P m = footOfLP(a,b,c);
    P u = (b-a) / (b-a).abs();
    double t = sqrt( c.r * c.r - dist * dist );
    ret.push_back( m + t * u );
    ret.push_back( m - t * u );
  }
  return ret;
}

int main2() {
  P p1;
  double r1;
  cin >> p1 >> r1;
  C c1 = C(p1, r1);
  int N; cin >> N;
  REP(i, N) {
    P a, b; cin >> a >> b;
    vector<P> ps = intersectionLC(a, b, c1);

    if (ps.size() == 1) {
      printf("%.10f %.10f %.10f %.10f\n", ps[0].x, ps[0].y, ps[0].x, ps[0].y);
    } else if (ps.size() == 2) {
      if (ps[1] < ps[0]) swap(ps[0], ps[1]);
      printf("%.10f %.10f %.10f %.10f\n", ps[0].x, ps[0].y, ps[1].x, ps[1].y);
    }
  }
  return 0;
}

int main() {

#ifdef LOCAL
  for (;!cin.eof();cin>>ws)
#endif
    main2();
  return 0;
}