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 <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <sstream>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <functional>
#include <bitset>
#include <deque>
#include <cmath>

using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
typedef long double LD;

#define rep(i, a, b) for(int i = a; i <= b; ++i)
#define dow(i, a, b) for(int i = a; i >= b; --i)
#define mem(a) memset(a, 0, sizeof(a))
#define mst(a, b) memset(a, b, sizeof(a))
#define sfi(a) scanf("%d", &a)
#define sfl(a) scanf("%lld", &a)
#define sfd(a) scanf("%lf", &a)
#define sfs(a) scanf("%s", a)
#define pb(a) push_back(a)
#define sync ios::sync_with_stdio(0); cin.tie(0);

const int MAX = 1e2 + 5;
const int L = 2;
const LL MOD = 10000;
const int dir[MAX][MAX] = {{0,1},{0,-1},{1,0},{-1,0},{-1,-1},{-1,1},{1,1},{1,-1}};

const double EPS = 1e-8;
const double PI = acos(-1.0);

typedef struct Point Point;
typedef struct Line Line;

int cmp(double x);
double sqr(double x);
double det(Point a, Point b);
double dot(Point a, Point b);
double dist(Point a, Point b);
Point rotate_point(Point p, double A);
bool parallel(Line a, Line b);
bool orthogonal(Line a, Line b);
Point PointProjLine(Point p, Line l, Point &ans);
Point reflect(Line l, Point p);
double dis_point_segment(Point p, Line l);
double dis_segment_segment(Line a, Line b);
Line point_make_line(Point a, Point b);
bool in_segment(Line l, Point p);
int dcmp(double k);
double mysqrt(double n);
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                  
struct Point
{
	double x, y;
	Point() {}
	Point(double a, double b): x(a), y(b) {}

	friend Point operator -(Point a, Point b)
	{
		return Point(a.x-b.x,a.y-b.y);
	}
	friend Point operator +(Point a, Point b)
	{
		return Point(a.x+b.x,a.y+b.y);
	}
	friend bool operator ==(Point a, Point b)
	{
		return cmp(a.x-b.x)==0 && cmp(a.y-b.y)==0;
	}
	friend Point operator *(Point a, double b)
	{
		return Point(a.x*b,a.y*b);
	}
	friend Point operator *(double a, Point b)
	{
		return Point(a*b.x,a*b.y);
	}
	friend Point operator /(Point a, double b)
	{
		return Point(a.x/b,a.y/b);
	}
	double norm()
	{
		return sqrt(sqr(x)+sqr(y));
	}
};

struct Line
{
	Point a, b;
	Line() {}
	Line(Point x, Point y): a(x), b(y) {}
};

bool parallel(Line a, Line b)
{
	return !cmp(det(a.a-a.b,b.a-b.b));
}
	
bool orthogonal(Line a, Line b)
{
	return !cmp(dot(a.a - a.b, b.a - b.b));
}

Point PointProjLine(Point p, Line l)
{
	Point ans;
	double r = dot((l.b-l.a),(p-l.a))/dot(l.b-l.a,l.b-l.a);
	ans = l.a + r*(l.b-l.a);
	return ans;
}

int cmp(double x)
{
	if(abs(x) < EPS)
		return 0;
	if(x > 0)
		return 1;
	return -1;
}

double dis_point_segment(Point p, Line l)
{
	if(cmp(dot(p-l.a,l.b-l.a))<0)
		return (p-l.a).norm();
	if(cmp(dot(p-l.b,l.a-l.b))<0)
		return (p-l.b).norm();
	return abs(det(l.a-p,l.b-p))/dist(l.a,l.b);
}

bool line_make_point(Line a, Line b, Point &res)
{
	if(parallel(a,b))
		return false;
	double s1 = det(a.a-b.a,b.b-b.a);
	double s2 = det(a.b-b.a,b.b-b.a);
	res = (s1*a.b-s2*a.a)/(s1-s2);
	return true;
}

double dis_segment_segment(Line a, Line b)
{
	Point res;
	if(line_make_point(a, b, res) && in_segment(a, res) && in_segment(b, res))
		return 0.;
	return min(min(dis_point_segment(b.a, a), dis_point_segment(b.b, a)), min(dis_point_segment(a.a, b), dis_point_segment(a.b, b)));
}

double sqr(double x)
{
	return x * x;
}

double det(Point a, Point b)
{
	return a.x*b.y-a.y*b.x;
}

double dot(Point a, Point b)
{
	return a.x*b.x+a.y*b.y;
}
double dist(Point a, Point b)
{
	return (a-b).norm();
}

Point rotate_point(Point p, double A)
{
	double tx = p.x, ty = p.y;
	return Point(tx*cos(A)-ty*sin(A),tx*sin(A)+ty*cos(A));
}

Point reflect(Line l, Point p)
{
	return p + ((PointProjLine(p, l) - p) * 2.0);
}

bool in_segment(Line l, Point p)
{
	bool fa = false, fb = false;
	if((cmp(p.x-l.a.x) != -1 && cmp(p.x-l.b.x) != 1) || (cmp(p.x-l.a.x) != 1 && cmp(p.x-l.b.x) != -1))
		fa = true;
	if((cmp(p.y-l.a.y) != -1 && cmp(p.y-l.b.y) != 1) || (cmp(p.y-l.a.y) != 1 && cmp(p.y-l.b.y) != -1))
		fb = true;
	return fa && fb;
}

int dcmp(double k)
{
	return k < -EPS ? -1 : k > EPS ? 1 : 0;
}

double mysqrt(double n)
{
	return sqrt(max(0.0, n));
}

void circle_cross_line(Point a, Point b, Point o, double r, Point ret[], int &num)
{
	double x0 = o.x, y0 = o.y;
	double x1 = a.x, y1 = a.y;
	double x2 = b.x, y2 = b.y;
	double dx = x2 - x1, dy = y2 - y1;
	double A = dx*dx+dy*dy;
	double B = 2*dx*(x1-x0)+2*dy*(y1-y0);
	double C = sqr(x1-x0)+sqr(y1-y0)-sqr(r);
	double delta = B*B-4*A*C;
	num = 0;
	if(dcmp(delta) >= 0)
	{
		double t1 = (-B - mysqrt(delta)) / (2*A);
		double t2 = (-B + mysqrt(delta)) / (2*A);
		ret[num++] = Point(x1 + t1*dx, y1 + t1*dy);
		ret[num++] = Point(x1 + t2*dx, y1 + t2*dy);
	}
	
}


int main()
{	
#ifdef LOCAL
	//~ freopen("in.txt", "r", stdin);
#endif

	Point o;
	double r;
	scanf("%lf%lf%lf", &o.x, &o.y, &r);
	int T;
	sfi(T);
	while(T--)
	{
		Line l;
		scanf("%lf%lf%lf%lf", &l.a.x, &l.a.y, &l.b.x, &l.b.y);
		Point ret[3];
		int num;
		circle_cross_line(l.a, l.b, o, r, ret, num);
		if(num == 1)
			ret[1].x = ret[0].x, ret[1].y = ret[0].y;
		if(ret[0].x > ret[1].x || (!cmp(ret[0].x - ret[1].x) && ret[0].y > ret[1].y))
			swap(ret[0], ret[1]);
		printf("%.6lf %.6lf %.6lf %.6lf\n", ret[0].x, ret[0].y, ret[1].x, ret[1].y);
	}
	return 0;
}