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:
#define __USE_MINGW_ANSI_STDIO 0
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define int ll
using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define PB push_back

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
const int MOD = 1000000007;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template <typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')';
  return out;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'[';
  REP(i, a.size()) {out<<a[i];if(i!=a.size()-1)out<<',';}
  out<<']';
  return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

const double EPS = 1e-8;

using R = long double;
using P = complex<R>;
using L = pair<P,P>;
using G = vector<P>;
struct C {
  P c; R r;
  C() {}
  C(const P &a, const R &b) : c(a), r(b) {}
};
struct S : public L {
  S() {}
  S(const P &a, const P &b) : L(a,b) {}
};

inline int sgn(const R& r) { return (r>EPS) - (r<-EPS); }
inline R dot(const P& a, const P& b) {
  return real(a)*real(b) + imag(a)*imag(b);
}
inline R det(const P& a, const P& b) {
  return real(a)*imag(b) - imag(a)*real(b);
}
inline P vec(const L& l) {return l.second - l.first;}
namespace std {
	bool operator < (const P& a, const P& b) {
		return sgn(real(a-b)) ? real(a-b) < 0 : sgn(imag(a-b)) < 0;
	}
	bool operator == (const P& a, const P& b) {
		return sgn(real(a-b)) == 0 && sgn(imag(a-b)) == 0;
	}
  bool cmp_y (const P& a, const P& b) {
    return sgn(imag(a-b)) ? imag(a-b) < 0 : sgn(real(a-b)) < 0;
  }
}

// P,L,Sについて入力
inline istream& operator>>(istream& is, P& p) {
  R x, y;
  is >> x >> y;
  p = P(x, y);
  return is;
}
inline istream& operator>>(istream& is, L& l) {
  P a, b;
  is >> a >> b;
  l = L(a, b);
  return is;
}
inline istream& operator>>(istream& is, S& s) {
  P a, b;
  is >> a >> b;
  s = S(a, b);
  return is;
}

// 射影
P inline projection(const L &l, const P &p) {
  R t = dot(p-l.first, l.first-l.second) / norm(l.first-l.second);
  return l.first + t*(l.first-l.second);
}
// 反射
P inline reflection(const L &l, const P &p) {
  return p + (R)2 * (projection(l, p) - p);
}

// 線分abから見たcの位置
enum CCW{LEFT=1, RIGHT=2, BACK=4, FRONT=8, ON_SEG=16};
int ccw(P a, P b, P c) {
	P p = (c-a)/(b-a);
	if(sgn(imag(p)) > 0) return LEFT;
	if(sgn(imag(p)) < 0) return RIGHT;
	if(sgn(real(p)) < 0) return BACK;
	if(sgn(real(p)-1) > 0) return FRONT;
	return ON_SEG;
}

// 垂直,平行
inline bool vertical(L a, L b) {return sgn(dot(vec(a), vec(b))) == 0;}
inline bool parallel(L a, L b) {return sgn(det(vec(a), vec(b))) == 0;}
inline bool eal(L a, L b) {return vertical(a,b) && parallel(a,b);}

// 交差判定
template<bool strict=false> inline bool intersect(const L&l1, const L&l2) {
  if(strict) return sgn(det(vec(l1),vec(l2))) != 0;
  return sgn(det(vec(l1),vec(l2))) != 0 || l1 == l2;
}
template<bool strict=false> inline bool intersect(const L&l, const S&s) {
  if(strict) det(s.first, vec(l)) * det(s.second, vec(l)) < 0;
  return det(s.first, vec(l)) * det(s.second, vec(l)) <= 0;
}
template<bool strict=false> inline bool intersect(const S&s1, const S&s2) {
  int ccw1 = ccw(s1.first, s1.second, s2.first) | ccw(s1.first, s1.second, s2.second);
  int ccw2 = ccw(s2.first, s2.second, s1.first) | ccw(s2.first, s2.second, s1.second);
  if(strict) return (ccw1 & ccw2) == (LEFT | RIGHT);
  return (ccw1 & ccw2) == (LEFT | RIGHT) || ((ccw1 | ccw2) & ON_SEG);
}
template<bool strict=false> inline bool intersect(const S&s, const P&p) {
  return ccw(s.first, s.second, p) == ON_SEG;
}
template<bool strict=false> inline bool intersect(const L&l, const P&p) {
  return ccw(l.first, l.second, p) == ON_SEG ||
          ccw(l.first, l.second, p) == FRONT ||
          ccw(l.first, l.second, p) == BACK;
}
int intersect(const C& a, const C& b) {
	R dist = sqrt(norm(a.c-b.c)), r1 = a.r + b.r, r2 = abs(a.r - b.r);
	if(sgn(r1-dist) < 0)  return 4;	// 円が離れている
	if(sgn(r1-dist) == 0) return 3;	// 外接
	if(sgn(r2-dist) < 0 && sgn(dist-r1) < 0) return 2; // 交差
	if(sgn(dist-r2) == 0) return 1; // 内接
	return 0;	// 内部に含む
}

// 距離
R dist(const S& s, const P& p) {
  P q = projection(s, p);
  if(sgn(dot(s.second-s.first, p-s.first)) <= 0) q = s.first;
  if(sgn(dot(s.first-s.second, p-s.second)) <= 0) q = s.second;
  return abs(p-q);
}
R dist(const S& a, const S& b) {
  if(intersect(a, b)) return 0;
  return min({dist(a, b.first), dist(a, b.second), dist(b, a.first), dist(b, a.second)});
}
R dist(const L& l, const P& p) {
  P q = projection(l, p);
  return abs(p-q);
}

// 交点 交差判定を先にすること!!!
inline P crosspoint(const L& l1, const L& l2) {
  R ratio = det(vec(l2), l2.first-l1.first)/det(vec(l2),vec(l1));
  return l1.first + vec(l1)*ratio;
}
// ToDo:そもそも交差しないとき
vector<P> crosspoint(C c, L l) {
	R d = dist(l, c.c), r = c.r;
	P m = projection(l, c.c);
	P x = sqrt(r*r-d*d)*vec(l)/abs(vec(l));
	vector<P> ret(2,m);
	ret[0] -= x;
	ret[1] += x;
	if(ret[1] < ret[0]) swap(ret[0], ret[1]);	//!!!
	return ret;
}
// vector<P> crosspoint(C a, C b) {
// 	double d = abs(a.p-b.p);
// 	double t = (a.r*a.r-b.r*b.r+d*d)/2/d, h = sqrt(a.r*a.r-t*t);
// 	P m = t/abs(b.p-a.p)*(b.p-a.p)+a.p;
// 	P n = n_vector(a.p-b.p);
// 	vector<P> ret(2, m);
// 	ret[0] -= h*n;
// 	ret[1] += h*n;
// 	sort(ret.begin(), ret.end());	//!!!
// 	return ret;
// }

// 面積 頂点が反時計回りに並んでいること
R area(const G& pol) {
  R ret = 0.0;
  REP(i, pol.size()) ret += det(pol[i], pol[(i+1)%pol.size()]);
  return (ret/2.0);
}

// 凸性の判定
bool isConvex(const G& pol) {
  REP(i, pol.size()) {
    if(sgn(det(pol[(i+1)%pol.size()]-pol[i], pol[(i+2)%pol.size()]-pol[i])) < 0) {
      return false;
    }
  }
  return true;
}

// 多角形と点の内包
// 2→in 1→on 0→out
int inPolygon(const G& pol, const P& p) {
  bool in = false;
  for (int i = 0; i < pol.size(); ++i) {
  	P a = pol[i] - p, b = pol[(i+1)%pol.size()] - p;
    if (imag(a) > imag(b)) swap(a, b);
    cout << i << " " << det(a, b) << endl;
    if (imag(a) <= 0 && 0 < imag(b) && sgn(det(a, b)) < 0) {
      cout << "rev" << endl;
      in = !in;
    }
    if (sgn(det(a, b)) == 0 && sgn(dot(a, b)) <= 0) return 1;
  }
  return in ? 2 : 0;
}

// 凸包 3点が一直線上に並ぶときに注意
// 凸包のうち一番左にある頂点の中で一番下の頂点から時計回り
G convex_hull(G ps) {
  int n = ps.size(), k = 0;
  sort(ps.begin(), ps.end());
  G r(2*n);
  for(int i=0; i<n; i++){
    while(k>1 && sgn(det(r[k-1]-r[k-2], ps[i]-r[k-2])) < 0) k--;
    r[k++] = ps[i];
  }
  for(int i=n-2,t=k; i>=0; i--){
    while(k>t && sgn(det(r[k-1]-r[k-2], ps[i]-r[k-2])) < 0) k--;
    r[k++] = ps[i];
  }
  r.resize(k-1);
  return r;
}

signed main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  P p;
  R r;
  cin >> p >> r;
  int q;
  cin >> q;

  C c(p, r);
  REP(i, q) {
    L l;
    cin >> l;
    vector<P> ret = crosspoint(c, l);
    cout << fixed << setprecision(9) << ret[0].real() << " " << ret[0].imag() << " " << ret[1].real() << " " << ret[1].imag() << endl;
  }

  return 0;
}