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;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define rep(i, a, b) for(int i = (a); i < (b); ++i)
#define per(i, a, b) for(int i = (b) - 1; i >= (a); --i)
#define sz(a) (int)a.size()
#define de(c) cout << #c << " = " << c << endl
#define dd(c) cout << #c << " = " << c << " "
#define all(a) a.begin(), a.end()
#define pw(x) (1ll<<(x))
#define endl "\n"
typedef long long ll;
typedef double db;
typedef pair<int, int> pii;
typedef vector<int> vi;

typedef db T;
const db eps = 1e-9 , pi = acosl(-1.);
int sgn(T x){return (x>eps)-(x<-eps);}
struct P{
  T x,y; P(){} P(T x,T y):x(x),y(y){}
  P operator - (const P&b) const {return P(x-b.x,y-b.y);}
  P operator + (const P&b) const {return P(x+b.x,y+b.y);}
  T operator * (const P&b) const {return x*b.x+y*b.y;}
  T operator / (const P&b) const {return x*b.y-y*b.x;}
  P operator * (const T&k) const {return P(x*k,y*k);}
  P operator / (const T&k) const {return P(x/k,y/k);}
	bool operator < (const P&b) const {return sgn(x-b.x)?x<b.x:y<b.y;}
	bool operator == (const P&b) const{return !sgn(x-b.x)&&!sgn(y-b.y);}
	P rot90(){return P(-y,x);}
};
T norm(P a){return a*a;}
T abs(P a) {return sqrtl(norm(a));}
P proj(P p,P a,P b){return (b-a)*((p-a)*(b-a)/norm(b-a))+a;}
P reflect(P p,P a,P b){return proj(p,a,b)*2-p;}
T cross(P o,P a,P b){return (a-o)/(b-o);}
int crossOp(P o,P a,P b){return sgn(cross(o,a,b));}
bool onPS(P p,P s,P t){return sgn((t-s)/(p-s))==0&&sgn((p-s)*(p-t))<=0;}
struct L{ P s,t;L(){} L(P s,P t):s(s),t(t){}};
P insLL(L a,L b){ // line x line
	P s = a.s - b.s , v = a.t - a.s , w = b.t - b.s;
	db k1 = s / w , k2 = w / v;
	if(sgn(k2) == 0) return abs(b.s - a.s) < abs(b.t - a.s) ? b.s : b.t;
	return a.s + v * (k1 / k2);
}
bool isSS(L a,L b){ // seg x seg , replace x->y to accelerate
	T c1=(a.t-a.s)/(b.s-a.s),c2=(a.t-a.s)/(b.t-a.s);
	T c3=(b.t-b.s)/(a.s-b.s),c4=(b.t-b.s)/(a.t-b.s);
	return sgn(c1) * sgn(c2) <= 0 && sgn(c3) * sgn(c4) <= 0 &&
		sgn(max(a.s.x,a.t.x) - min(b.s.x,b.t.x)) >= 0 &&
		sgn(max(b.s.x,b.t.x) - min(a.s.x,a.t.x)) >= 0 &&
		sgn(max(a.s.y,a.t.y) - min(b.s.y,b.t.y)) >= 0 &&
		sgn(max(b.s.y,b.t.y) - min(a.s.y,a.t.y)) >= 0;
}
db disPL(P p,L a){return fabs((a.t-a.s)/(p-a.s)) / abs(a.t-a.s);}
db disPS(P p,L a){ // p x seg dis
	if(sgn((a.t-a.s)*(p-a.s)) == -1) return abs(p-a.s);
	if(sgn((a.s-a.t)*(p-a.t)) == -1) return abs(p-a.t);
	return disPL(p,a);
}
db disSS(L a,L b){ // seg x seg dis
	if(isSS(a,b)) return 0;
	return min(min(disPS(a.s,b),disPS(a.t,b)),min(disPS(b.s,a),disPS(b.t,a)));
}
typedef vector<P> polygon;
polygon convex(polygon A){ // counter-clockwise , < : <=180 , <= : <180
  int n=sz(A),m=0;
  polygon B;B.resize(n<<1);
  sort(all(A));
  rep(i,0,n){
    while(m > 1 && sgn((B[m-1]-B[m-2])/(A[i]-B[m-2]))<0) --m;
    B[m++]=A[i];
  }
  int k = m;
  per(i,0,n-1){
    while(m > k && sgn((B[m-1]-B[m-2])/(A[i]-B[m-2]))<0) --m;
    B[m++]=A[i];
  }
  B.resize(m);
  if(sz(B) > 1) B.pop_back();
  return B;
}
T area(polygon A) { // multiple 2 with integer type
	T res=0;
	rep(i,0,sz(A)) res+=A[i]/(A[(i+1)%sz(A)]);
	return fabs(res) / 2;
}
bool isconvex(polygon A){ // counter-clockwise
	bool ok=1;int n=sz(A);
	rep(i,0,2) A.pb(A[i]);
	rep(i,0,n) ok&=((A[i+1]-A[i])/(A[i+2]-A[i]))>=0;
	return ok;
}
int inPpolygon(P p,polygon A){ // -1 : on , 0 : out , 1 : in
	int res=0;
	rep(i,0,sz(A)){
		P u=A[i],v=A[(i+1)%sz(A)];
		if(onPS(p,u,v)) return -1;
		T cross = sgn((v-u)/(p-u)) , d1 = sgn(u.y-p.y) , d2 = sgn(v.y-p.y);
		if(cross > 0 && d1 <= 0 && d2 > 0) ++res;
		if(cross < 0 && d2 <= 0 && d1 > 0) --res;
	}
	return res != 0;
}
T diameter(polygon A) { // longest distance
  int n=sz(A);if(n <= 1) return 0;
  int l=0,r=0;rep(i,1,n) (A[i]<A[l])&&(l=i),(A[r]<A[i])&&(r=i);
  db res=abs(A[l]-A[r]);int i=l,j=r;
  do (++((A[(i+1)%n]-A[i])/(A[(j+1)%n]-A[j])>=0?j:i))%=n,
    res=max(res,abs(A[i]-A[j]));
  while(i!=l||j!=r);
  return res;
}
polygon convexCut(polygon A,P s,P t){ // counter-clockwise , left hand of st
	int n=sz(A);
	polygon B;
	rep(i,0,n){
		P u=A[i],v=A[(i+1)%n];
		int d1 = sgn((t-s)/(u-s)) , d2 = sgn((t-s)/(v-s));
		if(d1 >= 0) B.pb(u);
		if(d1 * d2 < 0) B.pb(insLL(L(u,v),L(s,t)));
	}
	return B;
}
namespace NearestPoints{
  T solve(int l,int r,vector<P>&p){
    if(l == r) return 1e100;
    int m=(l+r)>>1;
    T Xm = p[m].x , lim = min(solve(l,m,p) , solve(m+1,r,p));
    inplace_merge(p.begin()+l,p.begin()+m+1,p.begin()+r+1,[&](P a,P b){return a.y<b.y;});
    vector<P> V;
    rep(i,l,r+1) if(fabs(p[i].x - Xm) <= lim) V.pb(p[i]);
    rep(i,0,sz(V)) rep(j,i+1,sz(V)){
      if(fabs(V[j].y - V[i].y) >= lim) break;
      T dis = abs(V[i]-V[j]);
      lim = min(lim,dis);
    }
    return lim;
  }
  T solve(vector<P> A){
    sort(all(A),[&](P a,P b){return a.x<b.x;});
    return solve(0,sz(A)-1,A);
  }
}
struct C{
	P o;T r;C(){} C(P o,T r):o(o),r(r){}
	bool operator == (const C&b) const {return o==b.o&&sgn(r-b.r)==0;}
};
int relCC(C A,C B){
	T dis = abs(A.o - B.o);
	if(sgn(dis - (A.r + B.r)) == 1) return 4;
	if(sgn(dis - (A.r + B.r)) == 0) return 3;
	if(sgn(dis - fabs(A.r - B.r)) == 1) return 2;
	if(sgn(dis - fabs(A.r - B.r)) == 0) return 1;
	return 0;
}
vector<P> insCL(C c,L a){
	db x = (a.s-c.o)*(a.t-a.s) , y = norm(a.t-a.s);
	db d = x * x - y * (norm(a.s-c.o) - c.r*c.r);
	vector<P> res;
	if(sgn(d) < 0) return res;
	d = max(d,0.);
	P mid = a.s - (a.t - a.s) * (x / y);
	P del = (a.t - a.s) * (sqrt(d) / y);
	return {mid - del,mid + del}; // dir : a.s -> a.t
}

C o;
P p;
db r;

int main() {
	std::ios::sync_with_stdio(0);
	std::cin.tie(0);
	//	freopen("a.in", "r", stdin);
	//	freopen("a.out", "w", stdout);
	cout << setiosflags(ios::fixed);
	cout << setprecision(10);
	cin >> p.x >> p.y >> r;
	o = C(p, r);
	int q;
	cin >> q;
	while(q--) {
		P a, b;
		cin >> a.x >> a.y >> b.x >> b.y;
		vector<P> r = insCL(o, L(a, b));
a = r[0], b = r[1];
		if(b.x < a.x || (b.x == a.x && b.y < a.y)) swap(r[0], r[1]);
		cout << r[0].x << " " << r[0].y << " " << r[1].x << " " << r[1].y << endl;
	}
	return 0;
}