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<iostream>
#include<cmath>
#include<iomanip>
#include<cstdio>
#include<algorithm>
using namespace std;
#define EPS 1e-10
static const int COUNTER_CLOCKWISE = 1;					//逆时针   
static const int CLOCKWISE = -1;							//顺时针
static const int ONLINE_BACK = 2;						//p2 在直线后面
static const int ONLINE_FRONT = -2;						//p2 在直线前面
static const int ON_SEGMENT = 0;						//p2 在直线上
int equals(double a, double b) { return fabs(a - b) < EPS; };
class Point {
public:
	double x, y;
	Point(double x=0, double y=0) :x(x), y(y) { };
	Point operator + (Point& p) {
		return Point(p.x + x, p.y + y);
	}
	Point operator - (Point& p) {
		
		return Point(x - p.x, y - p.y);
	}
	Point operator * (double k) {
		return Point(k*x, k*y);
	}
	double abs() {					//向量长度;
		return sqrt(x * x + y * y);
	}
};
typedef Point Vector;
double dot(Vector a, Vector b) {			//内积 x1*x2 + y1*y2
	return a.x * b.x + a.y * b.y;
}
double cross(Vector a, Vector b) {		  //外积  x1*y2 - x2*y1
	return a.x * b.y - a.y * b.x;
}
struct Segment           //线段
{
	Point a, b;
};
typedef Segment Line;   //线段表示直线；
class Circle {
public:
	Point c;
	double r;
	Circle(Point c = Point(), double x = 0) :c(c), r(x) {};
};
void Parallel_Orthogonal() {				//判断平行或正交
	Point a, b,c,d;
	Point e, f;
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a.x >> a.y >> b.x >> b.y>>c.x>>c.y>>d.x>>d.y;
		e = a - b;
		f = c - d;
		if (equals(dot(e, f), 0)) cout << "1" << endl;
		else if (equals(cross(e, f), 0))cout << "2" << endl;
		else cout <<"0" <<endl;
	}
}
Point Projection(Point& a, Point& b, Point& c) {		//计算投影点
	Point p;
	Vector v1 = b - a;
	Vector v2 = c - a;
	double len = dot(v1, v2);
	double len2 = len/ v1.abs();
	p.x = a.x + len2 / v1.abs() * v1.x;
	p.y = a.y + len2 / v1.abs() * v1.y;
	return p;
}
Point Reflection(Point& a, Point& b, Point& c) {	//算映像
	Point p = Projection(a, b, c);					//算出映射点
	return p*2 - c;									//映射点 是 该点与映像点中点  x + c = 2*p；
}
double getDistancePP(Point a, Point b) {				//两点距离;
	return ((a - b).abs());
}
double getDistancePL(Point a, Line b) {			//求点到直线距离 外积 = |a|.|b|.sin0  在直线上取两点，然后以其中一点为端点求出外
	Vector m = b.a - b.b;						//积的大小 再除以直线上的向量大小 则可以求解。
	Vector m2 = a - b.b;
	return abs(cross(m, m2) / m.abs());
}
int ccw(Point a, Point b, Point c) {			//三个点的位置关系
	Vector p = b - a;
	Vector p2 = c - a;
	if (cross(p, p2) > EPS) return COUNTER_CLOCKWISE;		//逆时针方向向外 结果为正
	if (cross(p, p2) < -EPS) return CLOCKWISE;				//顺时针方向为内 结果为负
	if (dot(p, p2) < -EPS) return ONLINE_BACK;
	if (dot(p, p2) > EPS&& p2.abs() > p.abs()) return ONLINE_FRONT;
	return ON_SEGMENT;
}
double getDistancePS(Point a, Segment b) {		//点到线段的距离;
	Point p1, p2;
	p1 = a - b.a;
	p2 = b.b - b.a;
	if (dot(p1, p2) < 0) {
		return p1.abs();
	}
	p1 = a - b.b;
	p2 = b.a - b.b;
	if (dot(p1, p2) < 0) {
		return p1.abs();
	}
	else {
		return getDistancePL(a, b);
	}
}
bool Intersection(Point a, Point b, Point c, Point d) {    //判断两线段是否相交  如果相交 则两个边的两个个端点会在另一条边的两边或线上
	return (ccw(a, b, c) * ccw(a, b, d) <= 0 && ccw(c, d, a) * ccw(c, d, b) <= 0);
}
Point Cross_Ponit(Point a, Point b, Point c, Point d) {	  //求两线段交点  通过面积求两边高  通过高求两边长度比例
	double s1 = cross(b - a, c - a);
	double s2 = cross(b - a, d - a);
	double d1 =  fabs(s1 * 2 / (b - a).abs());
	double d2 = fabs(s2 * 2 / (b - a).abs());
	Point p;
	p.x = d1 / (d1 + d2) * (d - c).x + c.x;
	p.y = d1 / (d1 + d2) * (d - c).y + c.y;
	return p;
}
double getDistanceSS(Point a, Point b, Point c, Point d) { //如果两者相交则直接返回0 否则是4个点到另一条直线最短的为距离
	if (Intersection(a, b, c, d)) return 0;
	double p1,p2;
	Segment s1,s2;
	s1.a = a;
	s1.b = b;
	s2.a = c;
	s2.b = d;
	p1 = min(getDistancePS(a,s2),getDistancePS(b,s2));
	p2 = min(getDistancePS(c, s1), getDistancePS(d, s1));
	return min(p1, p2);
}
void Cross_Points_of_Line(Line a, Circle c) {         //点与圆的交点。
	double d1 = getDistancePL(c.c,a);				//点到直线距离
	double d2 =sqrt (c.r * c.r - d1 * d1);			//求点到垂直点距离
	Point p = Projection(a.a,a.b,c.c );				//垂直点
	Point p2 = a.b - a.a;							//向量
	Vector v;
	v.x = d2 / p2.abs() * p2.x;
	v.y = d2 / p2.abs() * p2.y;
	Point p3, p4;
	p3 = p + v;
	p4 = p - v;
	
	if (p3.x - p4.x < -EPS) {
		printf("%.10f %.10f %.10f %.10f",p3.x,p3.y,p4.x,p4.y);
	}
	else if (p3.x - p4.x < EPS) {
		if (p3.y < p4.y) {
			printf("%.10f %.10f %.10f %.10f", p3.x, p3.y, p4.x, p4.y);
		}
		else {
			printf("%.10f %.10f %.10f %.10f", p4.x, p4.y, p3.x, p3.y);
		}
	}
	else {
		printf("%.10f %.10f %.10f %.10f", p4.x, p4.y, p3.x, p3.y);
	}
	cout << endl;
}
int main(void) {				
	Circle m;
	Line l;
	cin >> m.c.x >> m.c.y >> m.r;
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> l.a.x >> l.a.y >> l.b.x >> l.b.y;
		Cross_Points_of_Line(l, m);
	}
}