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 <cmath>
#include <utility>

using namespace std;

#define EPS (1e-10)
#define equals( A, B ) (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( x + p.x, y + p.y ); }
    Point operator - ( Point p ) { return Point( x - p.x, y - p.y ); }
    Point operator * ( double a ) { return Point( a * x, a * y ); }
    Point operator / ( double a ) { return Point( x / a, y / a ); }

    double abs() { return sqrt( norm() ); }
    double norm() { return x * x + y * y; }

    bool operator < ( const Point &p ) const {
	return ( x != p.x ) ? x < p.x : y < p.y;
    }

    bool operator == ( const Point &p ) const {
	return equals( x, p.x ) && equals( y, p.y ); 
    }

    double dot( Point a ) { return x * a.x + y * a.y; }
    double cross( Point a ) { return x * a.y - y * a.x; }
    double distance( Point a ) {
	return (*this - a).abs();
    }
};

typedef Point Vector;
static const int COUNTER_CLOCKWISE = 1;
static const int CLOCKWISE = -1;
static const int ONLINE_BACK = 2;
static const int ONLINE_FRONT = -2;
static const int ON_SEGMENT = 0;

class Line {
public:
    Point p1, p2;
    Line( Point p1 = Point(), Point p2 = Point() ): p1(p1), p2(p2){}
    // ?????´????????????( cos = 0 )
    bool isOrthogonal( Line a ) {
	return equals( 0.0, (p1 - p2).dot( a.p1 - a.p2 ) );
    }
    // ??????????????????( sin = 0 )
    bool isParallel( Line a ) {
	return equals( 0.0, (p1 - p2).cross( a.p1 - a.p2 ) );
    }

    Point projection( Point p ) {
	Vector v12 = p2 - p1;
	double r = v12.dot( p - p1 ) / v12.norm();
	return p1 + v12 * r;
    }

    Point reflection( Point p ) {
	return p + ( projection( p ) - p ) * 2.0;
    }

    double distance( Point p ) {
	Vector v12 = this->p2 -this->p1;
	Vector v10 = p - this->p1;
	
	return abs( v12.cross( v10 ) / v12.abs() );
    }

    double distanceSP( Point p ) {
	if ( (p - this->p1).dot( this->p2 - this->p1 ) < 0.0 ) {
	    return this->p1.distance( p );
	} else if ( (p - this->p2).dot( this->p1 - this->p2 ) < 0.0 ) {
	    return this->p2.distance( p );
	}
	else {
	    return distance( p );
	}
    }

    int ccw( Point p ) {
	Vector a = p2 - p1;
	Vector b = p - p1;
	if ( a.cross( b ) > EPS ) return COUNTER_CLOCKWISE;
	else if ( a.cross( b ) < -EPS ) return CLOCKWISE;
	else if ( a.dot( b ) < -EPS ) return ONLINE_BACK;
	else if ( a.norm() < b.norm() ) return ONLINE_FRONT;
	else return ON_SEGMENT;
    }

    bool intersect( Line l ) {
	return ( ( ccw( l.p1 ) * ccw( l.p2 ) <= 0 && l.ccw( p1 ) * l.ccw( p2 ) <= 0 ) );
    }

    Point crossPoint( Line l ) {
	Vector base = p2 - p1;
	Vector v1 = l.p1 - p1;
	Vector v2 = l.p2 - p1;
	double d1 = base.cross( v1 );
	double d2 = base.cross( v2 );	
	double t = d1 / ( d1 + d2 );

	return l.p1 + ( l.p2 - l.p1 ) * t;
    }
};

typedef Line Segment;


class Circle {
public:
    Point c;
    double r;

    Circle( Point c = Point(), double r = 0 ): c(c), r(r) {}

    pair<Point, Point> crossPoints( Line l ) {
	Point proj = l.projection( c ); // ?????????????????´???????°???±
	double base = sqrt( r * r - ( c - proj ).norm() );
	Vector e = ( l.p2 - l.p1 ) / ( l.p2 - l.p1 ).abs();
	if ( l.p2 < l.p1 ) e = e * -1; // x?????£????????????????????????
	return make_pair( proj - e * base, proj + e * base );
    }

};

int main()
{
    Circle c;
    int q;

    scanf("%lf %lf %lf", &c.c.x, &c.c.y, &c.r);
    scanf("%d", &q);

    for ( int i = 0; i < q; i++ ) {
	Point p1, p2;
	scanf("%lf %lf", &p1.x, &p1.y);
	scanf("%lf %lf", &p2.x, &p2.y);
	Line l = Line( p1, p2 );
	pair<Point, Point> pp = c.crossPoints( l );

	printf("%.10lf %.10lf ", pp.first.x, pp.first.y);
	printf("%.10lf %.10lf\n", pp.second.x, pp.second.y);
    }

    return 0;
}